Tri par sélection

Principe

On commence par rechercher le plus petit élement du tableau puis on l'échange avec le premier élement. Ensuite, on cherche le deuxième plus petit élement et on l'échange avec le deuxième élément du tableau et ainsi de suite jusqu'à ce que le tableau soit entièrement trié.

Voir l'animation proposée. lien

Algorithme et exemple d'implémentation en python

On peut formaliser l'algorithme du tri par sélection avec le pseudo-code suivant:

1
2
3
4
5
6
7
8

Tri_selection(t)
t: tableau de n éléments (t[0..n-1)
Pour i allant de 0 à n-2:
    idxmini = i
    Pour j allant de i+1 à n-1:
        Si t[j] < t[idxmini]:
            idxmini = j
    Echanger t[i] et t[idxmini]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def echange(t, i, j):
    """
    Permute les éléments situés aux index i et j du tableau t
    t: tableau non vide
    i, j: entiers dans l'intervalle [0, len(t)-1]
    """
    tmp = t[i]
    t[i] = t[j]
    t[j] = tmp

def tri_selection(t):
    """
    trie par ordre croissant les éléments de t
    """
    n = len(t)
    #Compléter le code

1
2
3
4

# Test
t = [5, 6, 1, 1, 15, 0, 4]
tri_selection(t)
assert t == [0, 1, 1, 4, 5, 6, 15]

Validité de l'algorithme

La terminaison est assurée car l'algorithme fait intervenir deux boucles bornées (boucle for).

Par ailleurs, la situation au $i^{ème}$ tour de boucle peut être représentée de la manière suivante:

Tous les éléments d'indice compris entre 0 et $i-1$ inclus sont triés et ils sont tous inférieurs ou égaux aux éléments de la partie non triée, se trouvant entre $i$ et $n-1$.
La preuve de cette proposition logique peut être délicate à établir en classe de 1re. Cette proposition est un invariant pour l'algorithme Tri_selection.

Trouver le bon invariant garantit que l'algorithme renvoie un résultat conforme aux spécifications et assure ainsi sa correction partielle. La combinaison de la correction partielle et de la terminaison permet de conclure à la correction totale de l'algorithme.

Complexité en temps

Le contenu de la boucle interne prend un temps d'exécution constant. Evaluons le nombre de fois qu'elle est exécutée.

Pour $i=0$, elle est exécutée $(n-1)-(0+1)+1=n-1$ fois.
Pour $i=1$, elle est exécutée $(n-1)-(1+1)+1=n-2$ fois.
Si on généralise, le nombre d'exécutions de la boucle interne est: $$(n-1)+(n-2)+\cdots +2+1$$ Cette somme correspond à la somme des termes consécutifs d'une suite arithmétique, dont la valeur pour $n>1$ est donnée par: $$\dfrac{n}{2}\times (n-1)=\dfrac{1}{2}n^2-\dfrac{1}{2}n$$

Pour une taille $n$ très grande de l'entrée, le terme en $n^2$ devient prépondérant. Autrement dit, le nombre d'opérations effectuées, donc le temps d'exécution, est proportionnel à $n^2$.
La complexité du tri par sélection est quadratique.

1
2
3
4

from time import time
top = time()
tri_selection(t)
print(time() - top)