Compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Les grandes valeurs « remontent » comme des bulles. Simple mais lent : ~n²/2 comparaisons.
Tri par sélection — Selection Sort
Comparaisons O(n²) · Échanges O(n)
Cherche le minimum du sous-tableau non trié et le place à sa position. Peu d'échanges (n au plus) mais toujours n²/2 comparaisons, même si déjà trié.
Tri par insertion — Insertion Sort
Pire O(n²) · Meilleur O(n)
Insère chaque élément à sa place dans la partie déjà triée. Très efficace sur un tableau presque trié (proche de O(n)). Utilisé pour les petits tableaux.
Tri fusion — Merge Sort
Comparaisons O(n log n) · Espace O(n)
Divise récursivement le tableau en deux, trie chaque moitié, puis fusionne. Complexité garantie n log n dans tous les cas, mais nécessite un tableau auxiliaire.
Tri rapide — Quick Sort
Moyen O(n log n) · Pire O(n²)
Choisit un pivot, partitionne autour, puis trie récursivement. Très rapide en pratique. Le pire cas O(n²) survient si le pivot est toujours mal choisi (tableau déjà trié).
🎯 Objectif
Comparer expérimentalement la complexité du tri à bulles et du tri fusion.
📋 Protocole
Régler N = 30, distribution « Aléatoire ».
Choisir « Tri à bulles », lancer et noter comparaisons + échanges.
Recréer le même tableau, choisir « Tri fusion », lancer et noter.