02 — Tableaux et Tris : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~55 min

---

Table des matières

1. Les tableaux
2. Recherche dans un tableau
3. Tris O(n²) : bulle, insertion, sélection
4. Tri rapide (QuickSort)
5. Tri fusion (Merge Sort)
6. Tri par tas (Heap Sort)
7. TimSort
8. Stabilité et « en place »
9. Tris linéaires : counting, radix, bucket
10. Comparaison complète des tris
11. Résumé

---

1. Les tableaux

1.1 Définition

Un tableau (array) est une structure contiguë en mémoire : les éléments sont stockés côte à côte. Le tableau T de n entiers occupe un bloc unique de n × 4 octets (si entiers 32 bits).

Diagramme en cours de génération...

1.2 Accès indexé — O(1)

L'adresse de l'élément T[i] est : adresse_base + i × taille_element. Calcul constant → accès O(1). C'est LA force du tableau.

T = [10, 20, 30, 40]
print(T[2])   # 30 — adresse = base + 2×taille → O(1)

1.3 Insertion et suppression — O(n) au milieu

• En fin : O(1) (amorti, si le tableau dynamique a de la place).
• Au début / au milieu : il faut décaler tous les éléments suivants → O(n).

def inserer(T, index, valeur):
    T.append(None)                # agrandir de 1
    for i in range(len(T) - 1, index, -1):   # décaler vers la droite
        T[i] = T[i - 1]
    T[index] = valeur
    return T

def supprimer(T, index):
    for i in range(index, len(T) - 1):        # décaler vers la gauche
        T[i] = T[i + 1]
    T.pop()
    return T

1.4 Tableau des opérations

---

2. Recherche dans un tableau

2.1 Recherche linéaire — O(n)

Parcourir l'ensemble. Simple, fonctionne sur toute liste, non triée incluse.

def recherche_lineaire(T, cible):
    for i, x in enumerate(T):
        if x == cible:
            return i
    return -1

2.2 Recherche binaire — O(log n)

Exige un tableau trié. On divise l'espace par 2 à chaque étape.

def recherche_binaire(T, cible):
    gauche, droite = 0, len(T) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if T[milieu] == cible:
            return milieu
        if T[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Pour n = 1 milliard : au plus 31 comparaisons (⌊log₂ n⌋ + 1).

2.3 Recherche par interpolation — O(log log n) en moyenne

Pour des valeurs uniformément distribuées, on estime la position :

mid = gauche + (cible - T[gauche]) * (droite - gauche) / (T[droite] - T[gauche])

def recherche_interpolation(T, cible):
    g, d = 0, len(T) - 1
    while g <= d and T[g] <= cible <= T[d]:
        if T[g] == T[d]:
            return g if T[g] == cible else -1
        m = g + (cible - T[g]) * (d - g) // (T[d] - T[g])
        if T[m] == cible:
            return m
        if T[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1

• Moyenne (distribution uniforme) : O(log log n).
• Pire cas (distribution défavorable) : O(n) — garder la binaire en secours.

2.4 Comparaison

---

3. Tris O(n²) : bulle, insertion, sélection

3.1 Tri à bulles (Bubble Sort)

Répéter : faire remonter le maximum en comparant les voisins.

def tri_bulles(T):
    n = len(T)
    for i in range(n):
        echange = False
        for j in range(n - i - 1):
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]
                echange = True
        if not echange:          # déjà trié
            break
    return T

• Temps : O(n²) pire, O(n) meilleur (liste triée, grâce au drapeau).
• Espace : O(1). Stable. Rarement utilisé — pédagogique.

3.2 Tri par insertion (Insertion Sort)

Construire la triée de gauche à droite en insérant chaque élément à sa place.

def tri_insertion(T):
    for i in range(1, len(T)):
        cle = T[i]
        j = i - 1
        while j >= 0 and T[j] > cle:
            T[j + 1] = T[j]
            j -= 1
        T[j + 1] = cle
    return T

• Meilleur cas : O(n) (déjà trié). Moyen/pire : O(n²).
• Espace : O(1). Stable. Excellent sur petites listes et listes quasi triées.
• C'est le tri utilisé par TimSort sur les petites sous-listes.

3.3 Tri par sélection (Selection Sort)

Sélectionner le minimum restant et le placer à la position courante.

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

• Temps : toujours O(n²) (pas de meilleur cas).
• Espace : O(1). Instable (l'échange peut inverser des égaux).
• Intérêt : minimum d'écritures (n échanges).

3.4 Comparaison des trois

---

4. Tri rapide (QuickSort)

4.1 Principe (diviser pour régner)

1. Choisir un pivot.
2. Partitionner : éléments < pivot à gauche, ≥ pivot à droite.
3. Récurser sur les deux moitiés.

Diagramme en cours de génération...

4.2 Partition de Lomuto

def partition_lomuto(T, bas, haut):
    pivot = T[haut]
    i = bas - 1
    for j in range(bas, haut):
        if T[j] <= pivot:
            i += 1
            T[i], T[j] = T[j], T[i]
    T[i + 1], T[haut] = T[haut], T[i + 1]
    return i + 1

4.3 Partition de Hoare (originale, souvent plus rapide)

def partition_hoare(T, bas, haut):
    pivot = T[(bas + haut) // 2]
    i, j = bas - 1, haut + 1
    while True:
        i += 1
        while T[i] < pivot:
            i += 1
        j -= 1
        while T[j] > pivot:
            j -= 1
        if i >= j:
            return j
        T[i], T[j] = T[j], T[i]

4.4 Récursion

def tri_rapide(T, bas=0, haut=None):
    if haut is None:
        haut = len(T) - 1
    if bas < haut:
        p = partition_lomuto(T, bas, haut)   # ou Hoare
        tri_rapide(T, bas, p - 1)
        tri_rapide(T, p + 1, haut)
    return T

4.5 Complexités et dangers

• Danger : pivot fixe (1er ou dernier élément) + liste triée → O(n²).
• Remèdes : pivot aléatoire (tri rapide randomisé), pivot médian-de-trois.
• Espace : O(log n) pile (récursif). Instable.

---

5. Tri fusion (Merge Sort)

5.1 Principe

1. Diviser en deux moitiés égales.
2. Trier chaque moitié récursivement.
3. Fusionner les deux moitiés triées en O(n).

5.2 Code

def tri_fusion(T):
    if len(T) <= 1:
        return T
    milieu = len(T) // 2
    gauche = tri_fusion(T[:milieu])
    droite = tri_fusion(T[milieu:])
    return fusion(gauche, droite)

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

5.3 Analyse

• Récurrence : T(n) = 2T(n/2) + O(n) → O(n log n) dans tous les cas.
• Espace : O(n) (tableau temporaire de fusion). Stable (si ≤ dans la fusion).
• Prédictible : indépendant de la distribution de l'entrée.

5.4 Version en place ? (délicate)

Le merge en place « simple » devient O(n log n) d'espace ou O(n²) en temps (naïf). En pratique on utilise un tableau auxiliaire. C'est pourquoi merge sort n'est pas « en place ».

---

6. Tri par tas (Heap Sort)

6.1 Principe

1. Construire un tas max (max-heap) à partir du tableau : le maximum est à la racine.
2. Échanger racine ↔ dernier élément, réduire la taille, tamiser (sift down).
3. Répéter jusqu'à épuisement.

Diagramme en cours de génération...

6.2 Code

def tamiser(T, n, i):
    plus_grand = i
    gauche = 2 * i + 1
    droite = 2 * i + 2
    if gauche < n and T[gauche] > T[plus_grand]:
        plus_grand = gauche
    if droite < n and T[droite] > T[plus_grand]:
        plus_grand = droite
    if plus_grand != i:
        T[i], T[plus_grand] = T[plus_grand], T[i]
        tamiser(T, n, plus_grand)

def tri_tas(T):
    n = len(T)
    for i in range(n // 2 - 1, -1, -1):   # construire le tas
        tamiser(T, n, i)
    for i in range(n - 1, 0, -1):         # extraire le max
        T[0], T[i] = T[i], T[0]
        tamiser(T, i, 0)
    return T

6.3 Analyse

• Construction du tas : O(n) (amorti).
• n extractions × O(log n) : O(n log n) dans tous les cas.
• Espace : O(1) (en place). Instable.
• Défaut : moins bon pour la localité de cache que le quick sort.

---

7. TimSort

7.1 Origine et importance

TimSort (Tim Peters, 2002) est le tri par défaut de Python (list.sort, sorted) et de Java (objets : Collections.sort, Arrays.sort). Aussi utilisé par Go (version modifiée), Swift, Rust.

C'est un merge sort hybride optimisé pour les entrées réelles (souvent quasi triées).

7.2 Principes

1. Runs : détecter les séquences déjà triées (croissantes ou décroissantes strictement).
2. Insertion sort sur les petits runs (seuil « minRun », typiquement 32-64).
3. Fusion : fusionner les runs avec une stack de runs et des invariants de taille (comme les puissances de Fibonacci dans la pile).
4. Galloping : lors de la fusion, quand un élément gagne consécutivement, chercher par recherche binaire sa position finale dans l'autre run (gagne beaucoup sur les données réelles).

Diagramme en cours de génération...

7.3 Complexités

À retenir : si vous triez en Python/Java, vous utilisez déjà TimSort — comprendre pourquoi il est si performant sur données réelles (adaptatif, stable, galop) est de l'ingénierie concrète.

---

8. Stabilité et « en place »

8.1 Tri stable vs instable

Un tri est stable si les éléments égaux conservent leur ordre relatif d'origine.

# Trions par lettre, puis par nombre
paires = [(1, 'b'), (2, 'a'), (1, 'a'), (2, 'b')]
# tri par nombre (stable) puis par lettre :
# [(1,'a'), (1,'b'), (2,'a'), (2,'b')]

Pourquoi c'est utile : trier par plusieurs critères — on trie par critère secondaire d'abord, puis par critère primaire ; seule la stabilité préserve le résultat du premier tri.

8.2 Tri en place vs non en place

• En place : espace O(1) au-delà de l'entrée (ou O(log n) pour la pile de récursion).
• Non en place : alloue O(n) d'espace supplémentaire (fusion, TimSort).

---

9. Tris linéaires : counting, radix, bucket

Les tris par comparaison ont une borne inférieure de Ω(n log n) (prouvée). Pour battre cette borne, il faut des hypothèses supplémentaires (valeurs entières bornées, distribution connue).

9.1 Counting sort — O(n + k)

Hypothèse : valeurs entières dans [0, k-1].

def counting_sort(T, k):
    compteurs = [0] * k
    for x in T:
        compteurs[x] += 1
    # cumuler
    for i in range(1, k):
        compteurs[i] += compteurs[i - 1]
    # placer (stable, en partant de la fin)
    resultat = [0] * len(T)
    for x in reversed(T):
        compteurs[x] -= 1
        resultat[compteurs[x]] = x
    return resultat

• Temps : O(n + k). Espace : O(n + k). Stable (version ci-dessus).

9.2 Radix sort — O(d·(n + k))

Hypothèse : entiers, tri par chiffres (d chiffres en base k), du moins significatif au plus significatif (LSD).

def tri_par_base(T, base=10):
    if not T:
        return T
    m = max(T)
    exp = 1
    while m // exp > 0:
        T = counting_sort_base(T, base, exp)
        exp *= base
    return T

def counting_sort_base(T, base, exp):
    compteurs = [0] * base
    for x in T:
        chiffre = (x // exp) % base
        compteurs[chiffre] += 1
    for i in range(1, base):
        compteurs[i] += compteurs[i - 1]
    resultat = [0] * len(T)
    for x in reversed(T):
        chiffre = (x // exp) % base
        compteurs[chiffre] -= 1
        resultat[compteurs[chiffre]] = x
    return resultat

• Temps : O(d × (n + k)) — pour des entiers 32 bits en base 256 : 4 passes → quasi linéaire.
• Espace : O(n + k). Stable.
• Pour n grands et entiers de taille fixe, il bat les tris par comparaison en pratique.

9.3 Bucket sort — O(n + m) en moyenne

Hypothèse : valeurs uniformément réparties dans [0, 1) (ou autre intervalle).

def bucket_sort(T, nb_boites=10):
    boites = [[] for _ in range(nb_boites)]
    for x in T:
        boites[int(x * nb_boites)].append(x)
    for b in boites:
        b.sort()                    # insertion ou récursion
    resultat = []
    for b in boites:
        resultat.extend(b)
    return resultat

• Moyenne : O(n) si les seaux sont équilibrés. Pire : O(n²) (tout dans un seau).
• Espace : O(n). Stable si le tri interne est stable.

---

10. Comparaison complète des tris

Guide de choix

Diagramme en cours de génération...

---

11. Résumé

1. Tableau : accès O(1), insertion/suppression O(n) au milieu.
2. Recherche : linéaire O(n) ; binaire O(log n) si trié ; interpolation O(log log n) si distribution uniforme.
3. Tris O(n²) : bulle (pédagogique), insertion (adaptatif, stable), sélection (instable).
4. QuickSort : O(n log n) en moyenne, O(n²) au pire — pivot aléatoire/médian-de-trois.
5. Merge sort : O(n log n) garanti, stable, O(n) d'espace.
6. Heap sort : O(n log n) garanti, en place, instable.
7. TimSort : adaptatif (O(n) sur quasi trié), stable, tri par défaut de Python/Java.
8. Tris linéaires : counting O(n+k), radix O(d(n+k)), bucket O(n+m) — avec hypothèses.
9. Choisir selon : taille, stabilité requise, mémoire, distribution, caractère critique du pire cas.

---

Exercices d'auto-évaluation

1. Pourquoi l'insertion au début d'un tableau coûte O(n) ?
2. Trouver 3 dans [1, 3, 5, 7, 9, 11] par recherche binaire — combien d'étapes ?
3. Quelle est la différence essentielle entre les partitions de Lomuto et de Hoare ?
4. Un tri stable, ça sert à quoi concrètement ? Donner un exemple.
5. Pourquoi le tri par comparaison est-il borné à Ω(n log n) ?
6. Quand utiliser radix sort plutôt que quick sort ?
7. Pourquoi TimSort est-il O(n) sur une liste déjà triée ?

Passez au quiz puis aux TP.