Exercice Algorithme : Le Tri par minimum successif
![](/images/thumb/46/default.png)
Enoncé de l'Exercice:
Le Tri par minimum successif
Principe
Le tri par minimum successif est ce que l'on appelle un tri par sélection :
Pour une place donnée, on sélectionne l'élément qui doit y être positionné
De ce fait, si on parcourt la tableau de gauche à droite, on positionne à chaque fois le plus petit élément qui se trouve dans le sous tableau droit
Ou plus généralement : Pour trier le sous-tableau t[i..nbElements] il suffit de positionner au rang i le plus petit élément de ce sous-tableau et de trier le sous-tableau t[i+1..nbElements]
Exemple :
Pour trier101, 115, 30, 63, 47, 20[1], on va avoir les boucles suivantes :
i=1101, 115, 30, 63, 47, 20[1]
i=220, 115, 30, 63, 47, 101[1]
i=320, 30, 115, 63, 47, 101[1]
i=420, 30, 47, 63, 115, 101[1]
i=520,30, 47, 63, 115, 101[1]
Donc en sortie :20, 30, 47, 63, 101, 155[1]
Travail à Faire :
- Créer une fonction qui pour soit capable de déterminer le plus petit élément (en fait l'indice du plus petit élément) d'un tableau à partir d'un certain rang
- Créer l’algorithme du Tri par minimum successif
1)
Fonction indiceDuMinimum (t : Tableau[1..MAX] d'Entier ; rang, nbElements : Naturel) : Naturel
Déclaration i, indiceCherche : Naturel
Début
indiceCherche
Pour i
si t[i]<t[indiceCherche] alors
indiceCherche
Fin si
Retourner indiceCherche
Fin pour
Fin
2)
L'algorithme de tri est donc :
procédure effectuerTriParMimimumSuccessif (E/S t : Tableau[1..MAX] d'Entier; E nbElements : Naturel)
Déclaration i,indice : Naturel
Début
Pour i
Indice
si i indice alors
echanger(t[i],t[indice])
Fin si
Fin pour
Fin