Home
About

Algorithme du tri par sélection

Cours/Algorithmie/Problème du tri/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 :

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. On appelle ces algorithmes in place car ils ne rendent rien, mais modifient les données en entrées.

Fonctionnement

On vérifie que l'algorithme fonctionne pour :

Preuve

Le principe de fonctionnement est clair. Il reste à prouver que c'est bien ce que l'algorithme sélection fait.

  1. la boucle for 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. comme la boucle for de la ligne 2 incrémente $i$, on a l'invariant de boucle :

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.

Complexités

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

Ligne à ligne :

  1. début de fonction : $\mathcal{O}(1)$
  2. une boucle de $n-1$ itérations
  3. une affectation $\mathcal{O}(1)$
  4. une boucle de $n-i-1$ itérations ($i$ est la variable définie ligne 2)
  5. un test et deux valeurs d'un tableau : $\mathcal{O}(1)$
  6. une affectation : $\mathcal{O}(1)$
  7. deux affectation et quatre valeurs d'un tableau : $\mathcal{O}(1)$

Le nombre d'itérations de la boucle for de la ligne 4 n'est pas constant, mais il décroît puisque $i$ augmente à chaque itération de la boucle for 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 :

$$ \begin{array}{lcl} C & = & \mathcal{O}(1) + \\ && (n-1) \cdot (\\ && \mathcal{O}(1) + \\ && (n-1) \cdot ( \\ && \mathcal{O}(1) + \\ && \mathcal{O}(1)) + \\ && \mathcal{O}(1)) \\ & = & \mathcal{O}(1) + (n-1) \cdot (\mathcal{O}(1) + (n-1) \cdot (\mathcal{O}(1))\\ & = & \mathcal{O}(n^2) \\ \end{array} $$

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

Proposition

La complexité de l'algorithme sélection est ($n$ est la taille du tableau passé en entrée) :

  • la complexité min vaut $\mathcal{O}(n^2)$
  • la complexité (max) vaut $\mathcal{O}(n^2)$
  • la complexité en moyenne vaut également $\mathcal{O}(n^2)$ (car les complexités min et max sont égales)

Variantes

TBD https://www.youtube.com/watch?v=_W0yUJlscRA

Sélection est identique à l'algorithme ci-dessous :

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

Pourquoi ?

Et celui ci tri dans le sens opposé :

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

pourquoi ?