Trier un tableau : sélection et insertion

Trier un tableau, c'est réordonner ses éléments du plus petit au plus grand. Les deux tris du programme construisent tous deux une partie triée à gauche du tableau, qui grandit d'une case à chaque tour ; ils diffèrent par la façon de la faire grandir.

Tri par sélection. Au tour i, on cherche le minimum de la partie non triée (des indices i à la fin) et on l'échange avec l'élément d'indice i.

def tri_selection(t):
    for i in range(len(t) - 1):
        m = i
        for j in range(i + 1, len(t)):
            if t[j] < t[m]:
                m = j
        t[i], t[m] = t[m], t[i]
        print(t)

t = [29, 11, 35, 7, 18]
tri_selection(t)

[7, 11, 35, 29, 18]
[7, 11, 35, 29, 18]
[7, 11, 18, 29, 35]
[7, 11, 18, 29, 35]

Le print(t) placé à la fin de chaque tour montre le tableau après chaque échange. Au deuxième tour, 11 est déjà le minimum de la partie non triée : il est « échangé » avec lui-même, le tableau ne change pas.

Tri par insertion. Au tour i, on prend l'élément t[i] et on l'insère à sa place dans la partie déjà triée, en décalant d'une case vers la droite les éléments plus grands que lui.

def tri_insertion(t):
    for i in range(1, len(t)):
        x = t[i]
        j = i
        while j > 0 and t[j - 1] > x:
            t[j] = t[j - 1]
            j = j - 1
        t[j] = x
        print(t)

t = [29, 11, 35, 7, 18]
tri_insertion(t)

[11, 29, 35, 7, 18]
[11, 29, 35, 7, 18]
[7, 11, 29, 35, 18]
[7, 11, 18, 29, 35]

Invariant de boucle. C'est une propriété vraie avant le premier tour et conservée par chaque tour ; à la sortie, elle prouve que le résultat est correct.

• Tri par sélection : « après le tour i, les i + 1 premiers éléments sont triés et sont inférieurs ou égaux à tous les éléments restants ». La seconde moitié de la phrase est essentielle : c'est elle qui garantit que ces éléments ne bougeront plus.
• Tri par insertion : « après le tour i, les i + 1 premiers éléments sont ceux du début du tableau d'origine, rangés dans l'ordre croissant ». Ils peuvent encore être décalés plus tard.

Terminaison. Les boucles for font un nombre fini de tours. La boucle while du tri par insertion s'arrête aussi : j diminue de 1 à chaque tour et la condition exige j > 0.

Coût. Le tri par sélection fait toujours le même nombre de comparaisons : (n − 1) + (n − 2) + … + 1 = n(n − 1)/2, quel que soit l'ordre de départ. Compté par programme :

def comparaisons_selection(n):
    c = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            c = c + 1
    return c

for n in [10, 20, 40]:
    print(n, comparaisons_selection(n))

10 45
20 190
40 780

Quand n double, le nombre de comparaisons est multiplié par environ 4 : le coût est quadratique. Le tri par insertion fait au pire n(n − 1)/2 comparaisons (tableau trié à l'envers) ; sur un tableau déjà trié, il n'en fait que n − 1.

Énoncé. Dérouler le tri par sélection sur [5, 3, 8, 1] et compter les comparaisons.

Au total, 3 + 2 + 1 = 6 comparaisons, c'est-à-dire 4 × 3 / 2. Le dernier élément n'a pas besoin de tour : quand tous les autres sont placés, il l'est aussi.