Quels algorithmes de tri connaissez-vous?

Algorithmes de tri principaux:

• Tri à bulles (Bubble Sort) : Algorithme simple mais inefficace, qui parcourt la liste plusieurs fois, échangeant les éléments adjacents s'ils sont dans le mauvais ordre.
• Tri par sélection (Selection Sort) : Trouve le plus petit (ou le plus grand) élément de la partie non triée de la liste et le place au début.
• Tri par insertion (Insertion Sort) : Construire progressivement une liste triée en insérant chaque nouvel élément à la bonne place dans la partie déjà triée.
• Tri par fusion (Merge Sort) : Algorithme récursif qui divise la liste en sous-listes, les trie, puis les fusionne.
• Tri rapide (Quick Sort) : Algorithme "diviser pour régner" qui choisit un élément pivot et redistribue les éléments pour que ceux inférieurs soient à gauche et ceux supérieurs à droite, en appliquant récursivement aux sous-listes.
• Tri Shell (Shell Sort) : Amélioration du tri par insertion utilisant des comparaisons à des distances plus grandes.
• Tri par tas (Heap Sort) : Utilise la structure de données "tas" pour un tri efficace.

Il existe aussi des algorithmes moins courants mais efficaces dans certains cas, comme le tri par comptage (Counting Sort), le tri radix (Radix Sort), et le tri par compartiments (Bucket Sort).

Temps d'exécution moyen des principaux algorithmes :

Algorithme de tri	Temps moyen
Tri à bulles	O(n²)
Tri par sélection	O(n²)
Tri par insertion	O(n²)
Tri par fusion	O(n log n)
Tri rapide	O(n log n)
Tri Shell	Dépend du pas
Tri par tas	O(n log n)

Exemple d'implémentation du tri rapide en Python :

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Choix de l'élément pivot
    left = [x for x in arr if x < pivot]  # Éléments inférieurs au pivot
    middle = [x for x in arr if x == pivot] # Éléments égaux au pivot
    right = [x for x in arr if x > pivot] # Éléments supérieurs au pivot
    return quicksort(left) + middle + quicksort(right) # Tri récursif et fusion