Pour terminer cette suite d’articles sur la programmation en Swift des schémas de programmes relatifs à la structure de file séquentielle, nous allons développer un programme de Tri d’une file séquentielle par recherche des extremas successifs.
Pour avons introduit dans les articles précédents
- L’action itérative permettant l’énumération d’une file
- Les séquences d’actions permettant de manipuler plusieurs files
- Dans le schéma de programme de Tri nous avons codé des actions itératives d’actions itératives.
La réalisation de ce Tri, particulièrement inefficace et très peu utilisé dans la pratique, est à considérer comme un exercice dans le cadre d’apprentissage de l’algorithmique.
Ce tri nécessite plusieurs parcours de la file, d’où les imbrications d’actions itératives. Le principe de cet algorithme est de chercher le premier élément minimum dans la file et de le ranger dans la nouvelle file. La recherche continue jusqu’à la fin de file pour trouver éventuellement et ranger tous les éléments minimum de même valeur. Dans un nouveau parcours on recherche ensuite un minimum partiel qui soit strictement supérieur au minimum précédent.
Nous sommes donc amenés à chercher un minimum supérieur à une valeur donnée du minimum précédent ainsi que le nombre d’éléments ayant cette valeur, en parcourant toute la file. On range ces éléments dans la nouvelle file et ce minimum devient le minimum précédent pour le pas suivant.
On a donc besoin de mettre en œuvre deux actions:
- MinMax: pour la recherche de l’élément minimun dans une file ou sous-file
- Nbmin : délivre la valeur du minimum courant et leur nombre
Le programme de calcul du nombre de minimum
func NombreDeMinimum(collection: File_Entier ,minPrec : Entier ,minCour : Entier ,nbMinCour: Entier ) -> (minimumCourant: Entier ,nombreDeMinimum: Entier ,minimumPrecedent: Entier) { var minimumCourant = minCour var nombreDeMinimum = nbMinCour let minimumPrecedent = minPrec var valeur : Entier = 0 let minMax = MinMax(collection) var min : Entier = minMax.max var nb: Entier = 0 Premier(collection) while !Dernier(collection){ valeur = Prendre(collection) if Super(valeur,element: minimumPrecedent) { if Egal(min, element: valeur) { nb = PlusUn(nb) } else { if Super(min, element: valeur) { nb = 1 min = valeur } } } Avancer(collection) } nombreDeMinimum = nb minimumCourant = min return ( minimumCourant, nombreDeMinimum, minimumPrecedent ) }
Le programme de Tri
func Tri (collection: File_Entier) -> File_Entier { var index = 0 var fileTriee: File_Entier = InitialiserCollection() let bornes = MinMax(collection) var minimumCourant = bornes.min var minimumPrecedent = 0 // bornes.max var nombreDeMinimum = 0 let zero : Entier = 0 let resultat = NombreDeMinimum(collection ,minPrec: minimumPrecedent ,minCour: minimumCourant ,nbMinCour: nombreDeMinimum) minimumPrecedent = resultat.minimumPrecedent minimumCourant = resultat.minimumCourant nombreDeMinimum = resultat.nombreDeMinimum while (nombreDeMinimum != zero) { index = 1 while InferOuEgal(index,element: nombreDeMinimum){ fileTriee = Ranger (fileTriee,element: minimumCourant) index = PlusUn(index) } minimumPrecedent = minimumCourant let resultat = NombreDeMinimum (collection ,minPrec: minimumPrecedent ,minCour: minimumCourant ,nbMinCour: nombreDeMinimum) minimumCourant = resultat.minimumCourant nombreDeMinimum = resultat.nombreDeMinimum } return fileTriee }
Fin de la série d’articles sur la traduction des schémas de programmes de file séquentielle en Swif