Aller au contenu

1NSI : Tri par Sélection⚓︎

Contenus Capacités Attendues Commentaires
Tri par Insertion,
par Sélection
Écrire un algorithme de tri.
Décrire un invariant de boucle
qui prouve la correction des tris
par insertion, par sélection.
La terminaison de ces algorithmes
est à justifier.
On montre que leur coût est
quadratique dans le pire cas.

Animation⚓︎

Considérons la liste [5, 4, 2, 1]
Voici le fonctionnement de l'algorithme :

Principe de L'Algorithme⚓︎

Le travail se fait essentiellement sur les indices.

  • du premier élément jusqu'à l'avant-dernier :
    • on considère que cet élément est l'élément minimum, on stocke donc son indice dans une variable indice du minimum.
    • on parcourt les éléments suivants, et si on repère un élémént plus petit que notre mininum on met à jour notre indice du minimum.
    • une fois le parcours fini, on échange l'élément de travail avec l'élément minimum qui a été trouvé.

L'Algorithme en Python⚓︎

Tri par sélection ❤

1
2
3
4
5
6
7
def tri_selection(l:list) :
    for k in range(len(l)-1):
        indice_min = k
        for i in range(k+1, len(l)) :
            if l[i] < l[indice_min]:
                indice_min = i
        l[k], l[indice_min] = l[indice_min], l[k]

Utilisation :

>>> ma_liste = [7, 5, 2, 8, 1, 4]
>>> tri_selection(ma_liste)
>>> ma_liste
[1, 2, 4, 5, 7, 8]

Terminaison de l'Algorithme⚓︎

1
2
3
4
5
6
7
def tri_selection(l:list) :
    for k in range(len(l)-1):
        indice_min = k
        for i in range(k+1, len(l)) :
            if l[i] < l[indice_min]:
                indice_min = i
        l[k], l[indice_min] = l[indice_min], l[k]

Est-on sûr que notre algorithme va s'arrêter (un jour) ?
Le programme est constitué de deux boucles for imbriquées.

Boucle for la plus intérieure⚓︎

Commençons par la boucle for la plus intérieure, i prenant des valeurs entre k+1 et n-1 inclus.
On note n = len(l)

Montrons que \(v=n-i\) est un variant de boucle :

  • \(v\) est un nombre entier
  • En entrant dans cette boucle for :
    \(v=n-(k+1) = (n - k) - 1 \geq 2 - 1 = 1 \gt 0\) car \(0 \leq k \leq n-2\)
  • \(v=n-i\) décroît strictement à chaque itération, car i est incrémenté de \(1\) à chaque itération, donc \(n-i\) est décrémenté de \(1\) à chaque itération
  • L'inégalité \(v\leq 0 \Leftrightarrow n-i \leq 0 \Leftrightarrow i \geq n\) provoque la sortie de la boucle for

Conclusion provisoire: Pour toute valeur de k, la boucle for la plus intérieure termine, car v est un variant de boucle.

Boucle for la plus extérieure⚓︎

Commençons par la boucle for la plus extérieure, k prenant des valeurs entre 0 et n-2 inclus.
On note n = len(l)

Montrons que \(v=(n-2)-k+1=n-k-1\) est un variant de boucle :

  • \(v\) est un nombre entier
  • En entrant dans cette boucle for :
    \(v=n-0-1 = n - 1 \geq 2 - 1 = 1 \gt 0\) en supposant que \(n \geq 2\), càd que la liste contienne au moins deux nombres.. ce que l'on peut toujours supposer (car sinon une liste ne contenant qu'un élément est déjà triée...)
  • \(v=n-k-1\) décroît strictement à chaque itération, car k est incrémenté de \(1\) à chaque itération, donc \(n-k-1\) est décrémenté de \(1\) à chaque itération
  • L'inégalité \(v\leq 0 \Leftrightarrow n-k-1 \leq 0 \Leftrightarrow k \geq n-1\) provoque la sortie de la boucle for

Conclusion: La boucle for la plus extérieure termine, car v est un variant de boucle.

Terminaison

L'algorithme du Tri par sélection termine

Correction de l'Algorithme⚓︎

1
2
3
4
5
6
7
def tri_selection(l:list) :
    for k in range(len(l)-1):
        indice_min = k
        for i in range(k+1, len(l)) :
            if l[i] < l[indice_min]:
                indice_min = i
        l[k], l[indice_min] = l[indice_min], l[k]

Nous savons maintenant que notre algorithme termine, mais est-on sûr que notre algorithme est correct : autrement dit, l'algorithme va-t-il bien trier notre liste ?

On note n = longueur(liste l) Il s'agit de choisir une propriété \(P\) qui soit un Invariant de Boucle, et qui dépende du (ou des) paramètres du problème/de la boucle. Ici, pour tout entier \(k\) compris entre \(0\) et \(n-2\), on peut choisir :

\(P(k)\) : « Au sortir de la \(k\)-ème itération, la sous-liste (de longueur \(k\)) des \(k\) premières valeurs est triée dans l'ordre croissant, ET les valeurs restantes sont toutes supérieures à la sous-liste déjà triée »

  • Initialisation : Après le 1er tour, càd lorsque \(k=1\), on place le minimum global de la liste en l[0] : La sous-liste constituée de l[0] (contenant \(1\) unique valeur) est donc triée, et toutes les valeurs restantes sont supérieures au minimum global. Donc \(P(1)\) est vraie.
  • Hérédité : Si, après la k-ème itération de la boucle for, la sous-liste des k premiers éléments est triée (des positions 0 à k-1) et les valeurs restantes sont toutes supérieures aux valeurs de la sous-liste, càd si \(P(k)\) est vraie, Alors, après une itération de plus de la boucle for (càd après la (k+1)-ième itération) l'algorithme insère à la position k le minimum des éléments restants (càd le minimum des éléments compris entre les positions k et n-1), dont on sait qu'il est forcément supérieur aux k premières valeurs comprises entre 0 et k-1. Finalement, après la k+1-ième itération, la sous-liste des k+1 premiers éléments est donc aussi triée (constituée de l[0], de l[1], .. et de l[k]), ET les éléments restants parmi les positions k+1 à n sont forcément supérieurs à tout élément de la sous-liste de positions 0 à k, càd que \(P(k+1)\) est vraie
  • Terminaison : Après la dernière (la n-2-ième) itération de la boucle for, la sous-liste des n-2 valeurs est donc triée, ET la valeur située à la position n-1 est supérieure à tout élément de la sous-liste de positions entre 0 et n-2. En conséquence, la liste de positions entre 0 et n-1 est bien triée : ceci prouve que l'algorithme est correct.

Complexité de l'algorithme⚓︎

Étude Expérimentale⚓︎

Proposer des mesures expérimentales pour déterminer la complexité du tri par Sélection. Pour mesurer les temps d'exécution, nous allons de nouveau utiliser la fonction timeit du module timeit. Rappelons nous que l'on doit modifier légèrement la fonction de tri, car sinon la liste sera triée dès le premier appel.

def tri_selection(L) :
    l = list(L) # pour ne pas modifier la liste passée en argument.
    for k ...

Nous allons fabriquer deux listes la et lb de taille \(100\) et \(200\) :

# Définir deux listes de nombres, dont la deuxième 'lb' est deux fois plus longue que la première 'la'
# on se place dans le pire des cas : chaque liste à trier est initialement dans l'ordre décroissant
la = [k for k in range(100,0,-1)]
lb = [k for k in range(200,0,-1)]

La mesure du temps moyen de tri pour ces deux listes est donnée par la fonction timeit du module timeit :

from timeit import timeit
ta = timeit("tri_selection(la)", globals=globals(), number=100)  # number = 1000000, par défaut
tb = timeit("tri_selection(lb)", globals=globals(), number=100)  # number = 1000000, par défaut
print(f"ta = {ta}")
print(f"tb = {tb}")

En comparant les temps de tri des listes la et lb, que pouvez-vous supposer sur la complexité du tri par sélection ?

-

Une liste à trier \(2\) fois plus longue prend \(4\) fois plus de temps : l'algorithme semble de complexité quadratique, en \(O(n^2)\)

Calcul du nombre d'opérations⚓︎

Dénombrons le nombre d'opérations \(C(n)\), dans le pire des cas (comme dans le meilleur des cas), pour une liste l de taille \(n\) (=len(l))

  • boucle for : elle s'exécute \(n-1\) fois.
  • deuxième boucle for imbriquée : elle exécute d'abord \(n-1\) opération, puis \(n-2\), puis \(n-3\)... jusqu'à \(1\).

Or :

\[\begin{align} C(n) &= 1+2+3+\dots+n-1 \\ &= \dfrac{n \times (n-1)}{2} \\ &=\dfrac {n^2-n}{2} \\ &=\dfrac{n^2}{2}-\dfrac{n}{2} \end{align} \]

Dans le pire des cas (de même que dans le meilleur des cas), donc, le nombre \(C(n)\) d'opérations effectuées / le coût \(C(n)\) / la complexité \(C(n)\) est mesurée par un polynôme du second degré en \(n\) dont le terme dominant (de plus haut degré) est \(\dfrac{n^2}{2}\), donc proportionnel au carré de la taille \(n\) des données en entrées, càd proportionnel à \(n^2\), càd en \(O(n^2)\). Ceci démontre que :

Complexité dans le pire des cas

Dans le pire des cas (liste triée dans l'ordre décroissant), le tri par sélection est de complexité quadratique, en \(O(n^2)\)

Dans le meilleur des cas (rare, mais il faut l'envisager) qui correspond ici au cas où la liste est déjà triée, on rentre toujours dans la deuxième boucle for : le nombre d'opérations est calculé de la même manière que dans le pire des cas (aucune différence)

Complexité dans le meilleur des cas

Dans le meilleur des cas (liste déjà triée), le tri par sélection est de complexité quadratique, en \(O(n^2)\)

Vérification expérimentale⚓︎

Insérez un compteur c dans votre algorithme pour vérifier le calcul précédent. On pourra renvoyer cette valeur en fin d'algorithme par un return c.

Résumé de la Complexité⚓︎

  • dans le meilleur des cas (liste déjà triée) : complexité quadratique en \(O(n^2)\)
  • dans le pire des cas (liste triée dans l'ordre décroissant) : complexité quadratique en \(O(n^2)\)

Bonus : comparaison des algorithmes de tri⚓︎

Une jolie animation permettant de comparer les tris :

image

Issue de ce site.