Chapitre 2 : Algorithmes de tri¶

Programme officiel (B.O.)¶

B.O. spécial n° 1 du 22 janvier 2019 - NSI Première

Contenus	Capacités attendues	Commentaires
Tri par sélection, tri par insertion.	Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction de l'algorithme.	La terminaison de ces algorithmes est assurée par la mise en œuvre d'une boucle bornée. On montre que le coût des deux algorithmes est quadratique dans le pire cas.

1. Pourquoi trier ?¶

Le tri est l'une des opérations les plus fondamentales en informatique. Trier des données permet ensuite de :

Faire une recherche dichotomique (beaucoup plus rapide)
Éliminer les doublons
Calculer la médiane
Afficher un classement, un palmarès

On étudie ici deux algorithmes simples qui trient un tableau en place (sans créer de nouveau tableau).

2. Tri par sélection¶

2.1 Principe¶

À chaque étape, on sélectionne le plus petit élément parmi ceux qui ne sont pas encore triés, et on le place à sa position définitive.

Chercher le minimum du tableau [0 .. n-1] et l'échanger avec l'élément en position 0
Chercher le minimum du tableau [1 .. n-1] et l'échanger avec l'élément en position 1
Ainsi de suite jusqu'à la fin

2.2 Déroulement d'un exemple¶

Tableau initial : [64, 25, 12, 22, 11]

Étape	Partie triée	Partie non triée	Min trouvé	Échange
1	`[]`	`[64, 25, 12, 22, 11]`	11 (indice 4)	64 ↔ 11
2	`[11]`	`[25, 12, 22, 64]`	12 (indice 2)	25 ↔ 12
3	`[11, 12]`	`[25, 22, 64]`	22 (indice 3)	25 ↔ 22
4	`[11, 12, 22]`	`[25, 64]`	25 (indice 3)	pas d'échange

Résultat : [11, 12, 22, 25, 64]

2.3 Implémentation¶

def tri_selection(tab):
    """Trie le tableau tab en place par sélection."""
    n = len(tab)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if tab[j] < tab[i_min]:
                i_min = j
        tab[i], tab[i_min] = tab[i_min], tab[i]

>>> t = [64, 25, 12, 22, 11]
>>> tri_selection(t)
>>> t
[11, 12, 22, 25, 64]

2.4 Correction (invariant de boucle)¶

Invariant : « Après l'itération i, les éléments tab[0..i] sont triés et sont les i+1 plus petits éléments du tableau. »

Initialisation (i = 0) : tab[0] contient le minimum du tableau entier → vrai
Conservation : à l'étape i, on place le minimum de tab[i..n-1] en position i. Les éléments tab[0..i-1] sont déjà triés et tous ≤ tab[i], donc tab[0..i] est trié → vrai
Terminaison : quand i = n-2, tout le tableau est trié

2.5 Complexité¶

La boucle interne parcourt : - n-1 éléments, puis n-2, puis n-3, ..., puis 1

Total de comparaisons : \((n-1) + (n-2) + ... + 1 = \frac{n(n-1)}{2}\)

La complexité est en O(n²), quel que soit le tableau (meilleur cas = pire cas).

3. Tri par insertion¶

3.1 Principe¶

Le tri par insertion fonctionne comme on trie un jeu de cartes dans sa main : on prend les cartes une par une et on insère chacune à sa bonne place dans la partie déjà triée.

L'élément en position 0 est « trié » (il est seul)
On prend l'élément en position 1 et on l'insère à sa place dans [0..0]
On prend l'élément en position 2 et on l'insère à sa place dans [0..1]
Ainsi de suite

3.2 Déroulement d'un exemple¶

Tableau initial : [5, 2, 4, 6, 1, 3]

Étape	Clé	Partie triée	Insertion	Résultat
1	2	`[5]`	2 < 5, décaler	`[2, 5, 4, 6, 1, 3]`
2	4	`[2, 5]`	4 < 5, 4 > 2	`[2, 4, 5, 6, 1, 3]`
3	6	`[2, 4, 5]`	6 > 5, en place	`[2, 4, 5, 6, 1, 3]`
4	1	`[2, 4, 5, 6]`	tout décaler	`[1, 2, 4, 5, 6, 3]`
5	3	`[1, 2, 4, 5, 6]`	3 entre 2 et 4	`[1, 2, 3, 4, 5, 6]`

3.3 Implémentation¶

def tri_insertion(tab):
    """Trie le tableau tab en place par insertion."""
    for i in range(1, len(tab)):
        cle = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j = j - 1
        tab[j + 1] = cle

>>> t = [5, 2, 4, 6, 1, 3]
>>> tri_insertion(t)
>>> t
[1, 2, 3, 4, 5, 6]

3.4 Correction (invariant de boucle)¶

Invariant : « Après l'itération i, le sous-tableau tab[0..i] contient les mêmes éléments qu'initialement, mais triés en ordre croissant. »

Initialisation (i = 1) : tab[0..1] contient 2 éléments en ordre → vrai
Conservation : on insère tab[i] à sa bonne place dans tab[0..i-1] (déjà trié), donc tab[0..i] est trié → vrai
Terminaison : quand i = n-1, tab[0..n-1] est trié

3.5 Complexité¶

Cas	Situation	Comparaisons	Complexité
Meilleur	Tableau déjà trié	n - 1	O(n)
Pire	Tableau trié à l'envers	\(\frac{n(n-1)}{2}\)	O(n²)
Moyen	Tableau aléatoire	\(\frac{n(n-1)}{4}\)	O(n²)

Le tri par insertion est plus rapide que le tri par sélection sur un tableau presque trié.

4. Comparaison des deux algorithmes¶

Critère	Tri par sélection	Tri par insertion
Complexité pire cas	O(n²)	O(n²)
Complexité meilleur cas	O(n²)	O(n)
Nombre d'échanges (pire cas)	O(n)	O(n²)
Stable (conserve l'ordre des égaux)	Non	Oui
Adaptatif (plus rapide si presque trié)	Non	Oui
En place (pas de mémoire supplémentaire)	Oui	Oui

Stabilité

Un tri est stable s'il conserve l'ordre relatif des éléments de même valeur. Par exemple, si deux élèves ont la même note, un tri stable conserve leur ordre initial.

5. Vérification expérimentale¶

On peut mesurer le temps d'exécution pour comparer les algorithmes :

import time
import random

def mesurer_temps(fonction_tri, taille):
    tab = [random.randint(0, 10000) for _ in range(taille)]
    debut = time.time()
    fonction_tri(tab)
    fin = time.time()
    return fin - debut

for n in [100, 1000, 5000, 10000]:
    t_sel = mesurer_temps(tri_selection, n)
    t_ins = mesurer_temps(tri_insertion, n)
    print(f"n={n:6d}  sélection: {t_sel:.4f}s  insertion: {t_ins:.4f}s")

On observe que quand n est multiplié par 10, le temps est multiplié par environ 100 (confirmation du O(n²)).

À retenir¶

Le tri par sélection cherche le minimum à chaque étape et le place en tête. Complexité : O(n²) dans tous les cas.
Le tri par insertion insère chaque élément à sa place dans la partie déjà triée. Complexité : O(n²) dans le pire cas, mais O(n) si le tableau est presque trié.
Les deux algorithmes trient en place (pas de tableau supplémentaire).
On prouve la correction d'un tri avec un invariant de boucle.
La terminaison est garantie par des boucles bornées.
Le tri par insertion est stable (conserve l'ordre des égaux), pas le tri par sélection.