Qu'est-ce que l'algorithme de tri rapide [expliqué avec des exemples]

Fonctionnement du tri rapide :

1. Diviser : Choisissez un élément pivot dans le tableau (souvent le dernier élément).

2. Partition : Réorganisez le tableau de telle sorte que tous les éléments inférieurs au pivot soient à gauche du pivot et que tous les éléments supérieurs au pivot soient à droite. L'élément pivot est dans sa position finale triée.

3. Récursivité : Répétez les deux étapes ci-dessus pour les sous-tableaux gauche et droit, en les décomposant de manière récursive jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément.

Exemple 1 :

Considérons le tableau [5, 3, 8, 2, 1, 4].

un. Diviser :choisissez le dernier élément, 1, comme pivot.

b. Partition:

- Réorganiser le tableau :[3, 2, 1, 5, 4, 8] (1 est dans sa position triée).

c. Récursion :

- Sous-tableau gauche :[3, 2, 1] (déjà trié)

- Sous-tableau droit : [5, 4, 8] (appliquer récursivement le tri rapide)

Après avoir appliqué le tri rapide aux deux sous-tableaux, le tableau trié final est : [1, 2, 3, 4, 5, 8].

Exemple 2 :

Tri d'un tableau plus grand

Considérons un tableau [7, 2, 9, 5, 3, 4, 1, 8, 6].

un. Diviser :choisissez le dernier élément, 6, comme pivot.

b. Partition:

- Réorganiser le tableau :[2, 5, 3, 4, 1, 7, 9, 6] (6 est dans sa position triée).

c. Récursion :

- Sous-tableau gauche :[2, 5, 3, 4, 1] (appliquer récursivement le tri rapide)

- Sous-tableau droit :[7, 9] (déjà trié)

Après avoir terminé les appels récursifs, le tableau trié est :[1, 2, 3, 4, 5, 6, 7, 8, 9].

Complexité temporelle :

- Meilleur cas :O(n log n)

- Cas moyen :O (n log n)

- Pire des cas :O(n^2) (se produit lorsque le tableau est déjà trié ou trié de manière inversée)

Dans l'ensemble, l'algorithme de tri rapide offre une solution de tri efficace avec une bonne complexité temporelle moyenne de O (n log n). Sa simplicité et sa polyvalence en ont fait un algorithme populaire pour trier les tâches dans différents langages de programmation.