Chapitre 9 : Tri par sélection.

Introduction :

Trier une liste en désordre : le problème semble banal, et pourtant la façon dont on s'y prend peut tout changer. Existe-t-il une bonne stratégie, et à quel prix ?

1. Trier

Trier des éléments dans un ordre croissant ou décroissant se produit souvent en informatique.

Par exemple :

On peut trier des scores
On peut trier une liste de personnes par ordre alphabétique.
On peut trier une liste de villes en fonction de leur population.

2. Exercice : tri manuel d'une liste de nombres.

À faire dans le cahier.

Soit la liste de nombres suivants : 3;5;8;2;5;9;23;5;1;8;5;4;0;6;4;5;34;1;4

Trier par ordre croissant les nombres de cette liste.
Expliquer votre méthode.

3. Tri par sélection.

Le tri par sélection est un algorithme de tri simple qui fonctionne en sélectionnant à chaque étape l'élément le plus petit (ou le plus grand) parmi les éléments non triés et en l'ajoutant à la partie triée de la liste.

L'algorithme de tri par sélection fonctionne comme suit :

Trouver l'élément le plus petit dans la liste non triée.
Échanger cet élément avec le premier élément de la liste non triée.
Répéter les étapes 1 et 2 pour le reste de la liste non triée.

Observe l'animation ci-dessous pour voir l'algorithme à l'œuvre :

Vitesse :

non trié partie triée minimum actuel élément comparé échange

Clique sur « Démarrer / Redémarrer » pour lancer l'animation.

4. Exercice : tri par sélection à la main.

À faire dans le cahier.

À la main :

Trier la liste [42, 17, 9, 87, 23, 56, 34, 71, 5] en mettant une ligne par étape avec un algorithme de tri par sélection.

On pourra mettre d'une couleur différente la partie triée et la partie non triée.

5. Pseudo code du tri par sélection

Pseudo-code

Algorithme TRI_SELECTION(tab)
    n ← longueur(tab)
    Pour k allant de 0 à n-2 faire
        imin ← k
        Pour i allant de k+1 à n-1 faire
            Si tab[i] < tab[imin] alors
                imin ← i
        échanger tab[k] et tab[imin]
    Renvoyer tab

6. Exercice : implémentation du tri par sélection.

En Python, il est possible d’échanger simplement la valeur de deux variables grâce à une affectation multiple.

L’instruction variable1, variable2 = variable2, variable1 permet d’échanger les valeurs de variable1 et variable2 sans utiliser de variable intermédiaire.

Compléter la fonction tri_selection ci-dessous pour trier une liste en utilisant l’algorithme du tri par sélection :

def tri_selection(tab): ... import random liste = [random.randint(1, 1000) for _ in range(20)] print(f"liste initiale : {liste}") tri_selection(liste) print(f"liste triée : {liste}")

>>>

7. Correction d’un algorithme et invariant de boucle

Pour prouver la correction (le fait qu'il soit correct) d’un algorithme utilisant une boucle, on introduit un invariant de boucle.

Un invariant de boucle est une propriété qui est :

vraie avant la première itération,
conservée à chaque tour de boucle,
encore vraie à la fin de la boucle.

Si l’invariant est vrai et que la boucle se termine, alors l’algorithme produit un résultat correct.

8. Exercice : invariant de boucle du tri par sélection.

À faire dans le cahier.

On veut prouver la correction de l’algorithme de tri par sélection à l’aide d’un invariant de boucle.

Rappel du pseudo-code :

Algorithme TRI_SELECTION(tab)
    n ← longueur(tab)
    Pour k allant de 0 à n-2 faire
        imin ← k
        Pour i allant de k+1 à n-1 faire
            Si tab[i] < tab[imin] alors
                imin ← i
        échanger tab[k] et tab[imin]
    Renvoyer tab

Propose un invariant de boucle pour la boucle externe (celle sur k).
Montre que l’invariant est vrai au début (initialisation).
Suppose l’invariant vrai à un rang k et montre qu’il reste vrai après une itération (conservation).
Explique pourquoi, à la fin de la boucle, l’invariant permet de conclure que tab est trié (conclusion).

9. Complexité du tri par sélection

Principe du tri par sélection

Le tri par sélection consiste à parcourir plusieurs fois le tableau pour placer, à chaque étape, le plus petit élément restant à la bonne position.

Nombre de comparaisons

Soit un tableau de taille \( n \).

Lors du premier passage, on compare \( n - 1 \) éléments pour trouver le minimum.
Lors du deuxième passage, on compare \( n - 2 \) éléments.
Et ainsi de suite, jusqu’à comparer 1 élément.

Le nombre total de comparaisons est donc :

\( (n - 1) + (n - 2) + \dots + 1 \)

Calcul de la somme

Cette somme est une somme bien connue :

\( (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} \)

Complexité temporelle

Le terme dominant de \( \frac{n(n - 1)}{2} \) est \( n^2 \).

On en déduit que la complexité du tri par sélection est : \( \mathcal{O}(n^2) \)

Remarque importante

Le nombre de comparaisons est le même quel que soit l’ordre initial du tableau.
Le tri par sélection a donc une complexité en \( \mathcal{O}(n^2) \) dans tous les cas.

Cela signifie que, globalement, si une liste est 2 fois plus longue qu'une autre, il sera 4 fois plus long de la trier.

Si la taille d'une liste est multipliée par 10, il sera 100 fois plus long de la trier etc.