Éclatement en monotonies
On appelle monotonie d’une file toute sous-file comprenant une suite d’éléments ordonnés suivant une relation d’ordre.
Exemple
soit la file définie par les nombres (10,14,16,7,8,100,101)
Elle comprend 3 monotonies dont la relation d'ordre sur des entiers croissants
(10,14,16)
(7,8)
(100,101)
On veut éclater une file en une suite de monotonies et ranger les monotonies en alternance sur deux files. Si l’on prend l’exemple précédent, on obtient la file1 et le file2 contenant respectivement les éléments (10,14,16,100,101) et (7,8)
La principale difficulté de cet algorithme réside dans la détermination de chaque monotonies. On détecte la fin d’une monotonie lorsque les valeurs de deux éléments consécutifs ne respecte pas la relation d’ordre. Dans le cas de monotonie de valeur entière croissante, on détecte une monotonie lorsque le premier élément rencontré après l’élément courant est inférieur à celui-ci.
Dans l’algorithme ci-dessous, la relation d’ordre se traduite par le prédicat Infer(x,y) afin de généraliser l’algorithme à des files dont le type des éléments est quelconque.
Schéma Programme Eclater-Monotonie
Interface
Objectif: Création de deux files contenant en alternance
les monotonies de la file pilote
Variable file : File
Variable file1 : File
Variable file2 : File
Résultat: Création de deux files
Remarque: file n'est pas modifiée
Fin-Interface
Procedure Eclater_Monotonie (file: File, file1: File, file2: File)
Déclaration
Variable valeur1 : Nombre
Variable valeur2 : Nombre
Variable Monotonie : Booléen
Instruction
Premier (file)
Premier (file1)
Premier (file2)
monotonie = Vrai
valeur1 = valeur2
TantQue Non (Dernier(file))
Faire
Prendre(file,valeur2)
Si Infer (valeur2,valeur1)
Alors
monotonie = Non Monotonie
Fin-Si
Si monotonie
Alors
Ranger(file1,valeur2)
Sinon
Ranger (file2,valeur2)
Fin-Si
valeur1 = valeur2
Fin-Faire
Fin-Instruction
Fin-Procedure
Fin_Schéma