Chapitre 9 : Tri par sélection.

Introduction :

Le tri par sélection est un algorithme de tri simple qui fonctionne en trouvant l'élément le plus petit (ou le plus grand, selon le tri) dans une liste non triée, puis en le plaçant au début.

Ce processus est répété pour le reste de la liste jusqu'à ce que tous les éléments soient triés. Bien qu'il soit facile à comprendre, cet algorithme n'est pas très efficace pour les grandes listes en raison de sa complexité en temps quadratique.

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 ville en fonction de sa population.

2. Exercice

A 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 .

A copier dans le cahier.

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.

4. Exercice :

A faire dans le cahier.

A 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

A copier dans le cahier.

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 :

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}")

Tests :

# Tests

Affichage :

Console:

>>>

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 :

A 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.