Algorithme du tri par sélection

Le tri par sélection est un algorithme simple qui fonctionne de la même manière quelque-soit le tableau en entrée. L'algorithme procède ainsi : à chaque itération de l'algorithme, on place à l'indice $i$ du tableau son $i$-ème plus petit élément.

On en déduit l'algorithme en pseudo-code suivant :

algorithme sélection(T: [entier]) → ∅:
    pour chaque i de [0, T.longueur[:  # boucle principale
        min_index ← i
        pour chaque j de [i + 1, T.longueur[:  # boucle intérieure
            si T[j] < T[min_index]:
                min_index ← j
        T[i], T[min_index] ← T[min_index], T[i]

def sélection(T):
    for i in range(len(T) - 1):
        min_index = i
        for j in range(i + 1, len(T)):
            if T[j] < T[min_index]:
                min_index = j
        T[i], T[min_index] = T[min_index], T[i]

L'algorithme sélection modifie le tableau passé en paramètre.

Fonctionnement

Preuve

Le principe de fonctionnement est clair :

1. la boucle pour chaque de la ligne 4 trouve l'indice du plus petit élément du tableau T[i:].
2. la ligne 7 échange le minimum du tableau T[i:] avec T[i]
3. la boucle principale fait recommencer cette procédure pour chaque indice de $T$.

On a alors clairement l'invariant de boucle :

À la fin de chaque étape $i$ de l'algorithme les $i$ plus petites valeurs du tableau sont triées aux $i$ premiers indices du tableau.

Qui permet de prouver qu'la fin de la boucle principale, le tableau est trié.

Complexités

On suppose que la taille du tableau est $n$.

Allons plus vite pour la complexité :

• toutes les instructions sont en $\mathcal{O}(1)$
• la boucle principale effectue $\mathcal{O}(n)$ itérations ($n-1$ exactement mais ce n'est pas important)
• la boucle intérieure fait $n-i-1$ itérations

Le nombre d'itérations de la boucle intérieure n'est pas constant, mais il décroît puisque $i$ augmente à chaque itération de la boucle pour chaque de la ligne 2. On peut alors utiliser la règle de croissance pour utiliser le maximum, $n-1$, pour le calcul de la complexité.

Ce qui donne une complexité de :

Le nombre d'itérations est constant quelque soit le tableau, on a donc :