Aller au contenu

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
  1. L'indice du plus petit élément de tab est 3 :

    tab = 12 14 17 11 18 15 13

    On échange cet élément avec tab[0] :

    tab = 11 14 17 12 18 15 13

  2. L'indice du plus petit élément de tab[1..] est à nouveau 3:

    tab = 11 14 17 12 18 15 13

    On échange cet élément avec tab[1] :

    tab = 11 12 17 14 18 15 13

  3. L'indice du plus petit élément de tab[2..] est 6 :

    tab = 11 12 17 14 18 15 13

    On échange cet élément avec tab[2] :

    tab = 11 12 13 14 18 15 17

  4. L'indice du plus petit élément de tab[3..] est 3 :

    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

  5. L'indice du plus petit élément de tab[4..] est 5 :

    tab = 11 12 13 14 18 15 17

    On échange cet élément avec tab[4] :

    tab = 11 12 13 14 15 18 17

  6. L'indice du plus petit élément de tab[5..] est 6 :

    tab = 11 12 13 14 15 18 17

    On échange cet élément avec tab[4] :

    tab = 11 12 13 14 15 17 18