Algorithme de tri par selection☘
tab est un tableau d'éléments porteur d'une relation d'ordre,
c'est-à-dire d'éléments que l'on peut comparer entre eux.
On désigne par n la taille du tableau tab donc les éléments de tab sont
numérotés de 0 à n-1.
Définition
On appelle « tri par sélection » un algorithme de tri d’un tableau
tab qui, dans chaque sous-tableau tab[i..], recherche la valeur d’un
extremum puis place cet extremum au début (ou à la fin) du sous-tableau.
Algorithme de tri par sélection du minimum☘
Cet algorithme nécessite de faire appel à deux algorithmes de référence sur les tableaux.
Cet algorithme est à effet de bord, c'est-à-dire qu'il modifie le contenu
interne du tableau tab.
Pour k allant de 1 à n-1 :
i_mini ← indice du minimum dans le sous-tableau tab[k..]
Echanger tab[k] et tab[i_mini]
Fin Pour
Application à un exemple☘
On considère le tableau suivant :
tab = |
14 | 12 | 17 | 11 | 18 | 15 | 13 |
-
L'indice du plus petit élément de
tabest3:tab=12 14 17 11 18 15 13 On échange cet élément avec
tab[0]:tab=11 14 17 12 18 15 13 -
L'indice du plus petit élément de
tab[1..]est à nouveau3:tab=11 14 17 12 18 15 13 On échange cet élément avec
tab[1]:tab=11 12 17 14 18 15 13 -
L'indice du plus petit élément de
tab[2..]est6:tab=11 12 17 14 18 15 13 On échange cet élément avec
tab[2]:tab=11 12 13 14 18 15 17 -
L'indice du plus petit élément de
tab[3..]est3:tab=11 12 13 14 18 15 17 On échange cet élément avec
tab[3](même si, ici, cela ne sert à rien) :tab=11 12 13 14 18 15 17 -
L'indice du plus petit élément de
tab[4..]est5:tab=11 12 13 14 18 15 17 On échange cet élément avec
tab[4]:tab=11 12 13 14 15 18 17 -
L'indice du plus petit élément de
tab[5..]est6:tab=11 12 13 14 15 18 17 On échange cet élément avec
tab[4]:tab=11 12 13 14 15 17 18