Exercices — Les algorithmes de tri

Pr. EL HADIQ Zouhair

6 exercices Python progressifs : du tri par sélection au tri rapide et au tri par fusion. Solution modèle et complexité données pour chacun.

Conseil. Cherchez la solution seul(e) avant de comparer. Pour chaque algorithme, identifiez sa complexité, s'il est en place et s'il est stable.

Écrire est_trie(L) qui renvoie True si L est triée par ordre croissant, False sinon.

est_trie([1, 2, 2, 5]) → True
est_trie([3, 1, 2])    → False
est_trie([])           → True

Solution :

def est_trie(L):
    for i in range(len(L) - 1):
        if L[i] > L[i + 1]:
            return False
    return True

Complexité : un seul parcours → O(n).

Écrire tri_selection(L) qui renvoie une liste triée, sans sorted ni .sort().

tri_selection([5, 2, 8, 1]) → [1, 2, 5, 8]
tri_selection([3, 3, 1])    → [1, 3, 3]

Solution :

def tri_selection(L):
    L = list(L)
    n = len(L)
    for i in range(n):
        imin = i
        for j in range(i + 1, n):
            if L[j] < L[imin]:
                imin = j
        L[i], L[imin] = L[imin], L[i]
    return L

Complexité : deux boucles imbriquées → O(n²). En place, non stable.

Écrire fusion(A, B) qui fusionne deux listes déjà triées en une liste triée.

fusion([1, 3, 5], [2, 4]) → [1, 2, 3, 4, 5]
fusion([], [1, 2])        → [1, 2]

Solution :

def fusion(A, B):
    C = []
    i, j = 0, 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            C.append(A[i]); i += 1
        else:
            C.append(B[j]); j += 1
    return C + A[i:] + B[j:]

Complexité : un parcours des deux listes → O(m+p).

En réutilisant fusion, écrire tri_fusion(L) qui renvoie L triée.

tri_fusion([5, 2, 8, 1, 3]) → [1, 2, 3, 5, 8]

Solution :

def tri_fusion(L):
    if len(L) <= 1:
        return list(L)
    m = len(L) // 2
    return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))

Complexité : T(n) = 2 T(n/2) + O(n) → O(n log n) garanti. Stable, mais O(n) d'espace.

Écrire partition(L) : pivot = premier élément, renvoie (petits, pivot, grands) avec petits ≤ pivot et grands > pivot. Pour L vide : ([], None, []).

partition([5, 2, 8, 1, 5]) → ([2, 1, 5], 5, [8])
partition([3])             → ([], 3, [])

Solution :

def partition(L):
    if not L:
        return ([], None, [])
    pivot = L[0]
    petits = [x for x in L[1:] if x <= pivot]
    grands = [x for x in L[1:] if x > pivot]
    return (petits, pivot, grands)

Complexité : un parcours → O(n). C'est l'étape clé du tri rapide.

Écrire tri_rapide(L) avec le premier élément comme pivot, par récursion.

tri_rapide([5, 2, 8, 1, 3]) → [1, 2, 3, 5, 8]
tri_rapide([3, 3, 1])       → [1, 3, 3]

Solution :

def tri_rapide(L):
    if len(L) <= 1:
        return list(L)
    pivot = L[0]
    petits = [x for x in L[1:] if x <= pivot]
    grands = [x for x in L[1:] if x > pivot]
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)

Complexité : O(n log n) en moyenne, O(n²) au pire (pivot mal choisi). En place (version classique), non stable.