Algorithme -7-

File séquentielle: Éclatement en monotonie
É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 
Programme Swift