[tab name=’Exercice Algorithme’]

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 :

1. 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
2. Créer l’algorithme du Tri par minimum successif

[/tab][tab name=’Correction’]

1)

Fonction indiceDuMinimum (t : Tableau[1..MAX] d’Entier ; rang, nbElements : Naturel) : Naturel

Déclaration i, indiceCherche : Naturel

Début

indiceCherche <– rang

Pour i <– rang+1 à nbElements faire

si t[i]<t[indicecherche] alors<= » » p= » »>

indiceCherche <– i

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 <– 1 à nbElements-1 faire

Indice <– indiceDuMinimum(t,i,nbElements)

si i indice alors

echanger(t[i],t[indice])

Fin si

Fin pour

Fin

[/tab][end_tabset skin= »ginger » ]