Chapitre 12 : Algorithmes de tri⚓︎

A. Le tri par sélection⚓︎

A savoir

I. Principe du tri par sélection⚓︎

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Appelé « selection sort » en anglais, c'est l'algorithme le plus simple qui soit.

À chaque étape du tri par sélection, le tableau se sépare en deux parties :

Ce qui est déjà trié est à gauche : au début, la partie triée n'existe pas puisque le tableau est non ordonné.
Ce qui n'est pas encore trié est à droite.

Le principe du tri par sélection est le suivant :

On cherche d'abord le plus petit élément dans la partie non triée du tableau.
On échange avec le premier élément de la partie non triée cet échange pouvant nécessiter l'utilisation d'une variable de passage.
On recommence l'étape 1 sur la partie non triée du tableau.

▶️ Capsule : le tri par sélection

II. Algorithme du tri par sélection⚓︎

DÉBUT
    n ← longueur de tab
    POUR i de 0 à n-1 FAIRE
        ind_min ← i
        POUR j de i+1 à n FAIRE
            SI tab[j] < tab[ind_min] ALORS
                ind_min ← j
        SI ind_min ≠ i ALORS
            échanger tab[i] et tab[ind_min]
    FIN

III. Efficacité du tri par sélection⚓︎

Pour une taille \( n \) de tableau donnée, l'algorithme effectuera toujours le même nombre de comparaisons : il n'y a pas de pire ou meilleur cas (tous les tableaux sont des pires cas). Cela vient du fait que l'on connaît toujours à l'avance le nombre de tours de boucle puisqu'il s'agit de deux boucles imbriquées.

Au 1er passage dans la boucle (pour \( i=0 \)), il y a \( n-1 \) comparaisons dans la recherche du plus petit élément.
Au 2ème passage (pour \( i=1 \)), il y en a \( n-2 \) comparaisons.
Ainsi de suite...
Au dernier passage (pour \( i=n-2 \)), il n'y a plus qu'une comparaison (les deux dernières cases).

Il y a donc en tout \((n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2}\) comparaisons à faire dans le pire cas (dans tous les cas !) : on retrouve donc aussi un coût de l'ordre de \( n^{2} \) puisque \(\frac{n(n-1)}{2}=\frac{n^{2}-n}{2}=\frac{n^{2}}{2}-\frac{n}{2}\).

Le tri par sélection a donc un coût quadratique dans le pire cas, c'est-à-dire de l'ordre de \( n^{2} \) (où \( n \) = taille du tableau). Cela signifie que si on multiplie par \( k \) la taille du tableau, alors le temps de calcul pour faire le tri est multiplié par \( k^{2} \). Il y a toujours \(\frac{n(n-1)}{2}\) comparaisons à faire dans tous les cas.

IV. Implémentation de l'algorithme en Python⚓︎

En Python, l'algorithme peut s'implémenter de la façon suivante :

def selection_sort(tab):
    n = len(tab)
    for i in range(n-1):
        ind_min = i
        for j in range(i+1, n):
            if tab[j] < tab[ind_min]:
                ind_min = j
        if ind_min != i:
            tab[i], tab[ind_min] = tab[ind_min], tab[i]

On peut également utiliser des boucles while à la place des boucles for.

B. Le tri par insertion⚓︎

A savoir

I. Principe du tri par insertion⚓︎

La méthode du tri par insertion s'apparente à celle utilisée pour trier ses cartes dans un jeu : on prend une carte puis la deuxième que l'on place en fonction de la première, ensuite la troisième que l'on insère à sa place en fonction des deux premières et ainsi de suite.

Dans le tri par insertion, le tableau se sépare en deux parties :

Ce qui est déjà trié est à gauche : au début, il n'y a qu'un nombre, le premier du tableau.
Ce qui n'est pas encore trié est à droite.

À chaque étape :

On prend le premier nombre de la partie non triée.
On mémorise cet élément.
On décale les éléments de la partie triée vers la droite tant que l'élément mémorisé est plus petit.
On insère exactement l'élément mémorisé à sa juste place dans la partie triée.

▶️ Capsule : le tri par insertion

VARIABLES
    tab : tableau d'entiers
DÉBUT
    n ← longueur(tab)
    POUR i ALLANT DE 1 à n FAIRE
        courant ← tab[i]
        j ← i
        TANT QUE j > 0 ET QUE courant < tab[j-1]
            tab[j] ← tab[j-1]
            j ← j-1
        tab[j] ← courant
    FIN

III. Efficacité du tri par insertion⚓︎

L'efficacité d'un algorithme correspond à son coût en termes d'opérations élémentaires dans le pire cas. Pour simplifier cette étude, nous n'allons étudier ici que le nombre de comparaisons du tri par insertion. Dans le cadre du tri par insertion, le pire des cas est d'avoir un tableau trié par ordre décroissant puisqu'il faut aller insérer chaque élément en première position : cela implique de le comparer à tous les éléments qui le précèdent.

Pour un tableau de taille \( n \) trié par ordre décroissant (pire cas), on a :

Au premier passage dans la boucle : il y a 1 comparaison à faire (tab[1] est comparé à tab[0]).
Au deuxième passage : il y a 2 comparaisons à faire (tab[2] est comparé successivement à tab[1] et tab[0]).
Ainsi de suite...
Au dernier passage (\( i=n-1 \)) : il y a \( n-1 \) comparaisons à faire (tab[n-1] est comparé successivement à tab[n-2], tab[n-3], ..., tab[0]).

Il y a donc en tout \((n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2}\) comparaisons à faire dans le pire cas (dans tous les cas !) : on retrouve donc un coût de l'ordre de \( n^{2} \) puisque \(\frac{n(n-1)}{2}=\frac{n^{2}-n}{2}=\frac{n^{2}}{2}-\frac{n}{2}\).

Le tri par insertion a donc un coût quadratique dans le pire cas, c'est-à-dire de l'ordre de \( n^{2} \) (où \( n \) = taille du tableau). Cela signifie que si on multiplie par 3 la taille du tableau, alors le temps de calcul pour faire le tri est multiplié par \( 3^{2} \). Il y a toujours \(\frac{n(n-1)}{2}\) comparaisons à faire dans tous les cas.

IV. Implémentation de l'algorithme en Python⚓︎

En Python, l'algorithme peut s'implémenter de la façon suivante :

def insertion_sort(tab):
    n = len(tab)
    for i in range(1, n):
        courant = tab[i]
        j = i
        while j > 0 and courant < tab[j-1]:
            tab[j] = tab[j-1]
            j = j-1
        tab[j] = courant

On peut également utiliser des boucles while à la place des boucles for.