C11.1 : Rappels sur les algorithmes de tri de première

Tri par sélection

Principe

Dans cet algorithme, il s'agit de rechercher la plus petite valeur de la partie non triée de la liste et de l'insérer à la suite de la partie déjà triée de la liste... puis de recommencer.

Lien : Visualisation du principe du tri par sélection.

Codage de l'algorithme "en place"

Proposer une fonction, basée sur l'algorithme de tri par sélection, qui permet de trier "en place" une liste passée en paramètre, c'est à dire en modifiant directement cette liste.

Afficher la correction 
from random import randint

def tri_selection(L):
    '''
    Tri la liste L du plus petit au plus grand
    param L: (list) Liste de nombres entiers
    effets de bord : le paramètre L est modifiée
    '''
    for i in range(0, len(L)-1):
        pos_max = i
        for j in range(i+1, len(L)):
            if L[j] < L[pos_max]:
                pos_max = j
        L[pos_max], L[i] = L[i], L[pos_max]

# -----Programme principal-----
liste = [randint(0,99) for _ in range(20)]
print(liste)
tri_selection(liste)
print(liste)

Coût de l'algorithme

1) Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?

2) Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?

Afficher la correction

L'algorithme fait toujours le même nombre de comparaisons, quelque soit la liste de départ.

Si on note \(n\) la longueur de la liste à trier, dans ce cas il fait \((n-1) + (n-2) + ... + 3 + 2 + 1 = \dfrac{n×(n-1)}{2}\).

Remarque : \(1 + 2 + 3 + ... + k = \dfrac{k×(k+1)}{2}\)

Le coût de l'algorithme est proportionnel à \(n^2\), on dit que le coût est quadratique.

Preuve de l'algorithme

1) Démontrer la terminaison de l'algorithme.

2) Proposer un invariant pour chacune des deux boucles.

Afficher la correction

1)

La preuve de la terminaison de l'algorithme est immédiate car l'algorithme est composé de deux boucles for.

2)

L'invariant pour la boucle de recherche de la position du plus grand élément dans la partie non triée (boucle interne) est :

« L'élément à la position pos_max est plus grand que tous les éléments de i à j ».

L'invariant pour la boucle qui permet de trier un élément supplémentaire (boucle externe) est :

« La partie du tableau de 0 à i est triée ».

Tri par insertion

Principe

Dans cet algorithme, il s'agit de prendre les valeurs de la liste les unes après les autres et de les insérer de façon à ce qu'elles forment une portion triée de liste.

Lien : Visualisation du principe du tri par insertion.

Codage de l'algorithme "en place"

Proposer une fonction, basée sur l'algorithme de tri par insertion, qui permet de trier "en place" une liste passée en paramètre, c'est à dire en modifiant directement cette liste.

Afficher la correction 
from random import randint

def tri_insertion(L):
    '''
    Tri la liste L du plus grand au plus petit
    param L: (list) Liste de nombres entiers
    effets de bord : le paramètre L est modifiée
    '''
    for i in range(1, len(L)):
        elt = L[i]
        p = i-1
        while elt < L[p] and p >= 0:
            L[p+1] = L[p]
            p = p - 1
        L[p+1] = elt

# -----Programme principal-----
liste = [randint(0,99) for _ in range(20)]
print(liste)
tri_insertion(liste)
print(liste)

Coût de l'algorithme

1) Pour quelle configuration de liste l'algorithme fait-il le moins de comparaison ? Dans ce cas combien en fait-il ?

2) Pour quelle configuration de liste l'algorithme fait-il le plus de comparaison ? Dans ce cas, combien en fait-il ?

Afficher la correction

1)

L'algorithme fait le moins de comparaison lorsque la boucle est déjà triée.

Si on note n la longueur de la liste à trier, dans dans ce cas il fait n-1 comparaisons.

Dans ce cas, le coût de l'algorithme est proportionnel à n, on dit que le coût est linéaire.

2)

L'algorithme fait le plus de boucle lorsque la liste est totalement inversée par rapport à l'ordre souhaité.

Si on note n la longueur de la liste à trier, dans ce cas il fait \(1 + 2 + 3 + ... + (n-1) = \dfrac{(n-1)×n}{2}\).

Remarque : \(1 + 2 + 3 + ... + k = \dfrac{k×(k+1)}{2}\)

Dans ce cas, le coût de l'algorithme est proportionnel à \(n^2\), on dit que le coût est quadratique.

Preuve de l'algorithme

1) Démontrer la terminaison de l'algorithme.

2) Proposer un invariant pour chacune des deux boucles.

Afficher la correction

1)

■ Pour la boucle for

La boucle for se termine nécessairement

■ Pour la boucle while

Le variant convergeant de boucle est p.

En effet :

  • - Tout d'abord, notons que p commence à i-1 ;
  • - Par ailleurs, dans la boucle, p diminue de 1 à chaque itération donc les valeurs de p forment une suite d'entiers strictement décroissante ;
  • - Or lorsque la valeur de p n'est plus positive ou nulle, on sort de la boucle ;
  • - Donc on sort nécessairement de la boucle.

2)

• Pour la boucle for, l'invariant de boucle est : « La partie de la liste de 0 à i est triée ».

• Pour la boucle while, de façon simplifiée, l'invariant de boucle est la proposition suivante : « La partie de la liste de 0 à p-1 et la partie de la liste de p+1 à i sont triées ».
Remarque : il faut un énoncé plus rigoureux pour les cas limites.

Pour aller plus loin

Lien : Algorithmes de tri

Lien : Algorithmes de tri animés

Lien : Sorting Algorithms Animations

 

Lien : Comparaison de quelques algorithmes de tri