Cela se produit lorsque le tableau d'entrée est déjà trié (par ordre croissant ou décroissant) ou presque. Lorsque le tableau est trié, le pivot sera toujours l'élément le plus petit (ou le plus grand). Il en résulte des partitions très déséquilibrées.

Par exemple, si le tableau est trié par ordre croissant et que le premier élément est toujours le pivot :

1. Le premier élément est choisi comme pivot.

2. Tous les autres éléments sont supérieurs au pivot, ils se retrouvent donc tous dans la bonne partition.

3. La partition de gauche est vide.

4. L'appel récursif est ensuite effectué sur un sous-tableau de taille « n-1 ».

Ce processus se répète, conduisant à une profondeur de récursion de « n ». A chaque niveau `i` de la récursion, nous effectuons des comparaisons `n - i`. Le nombre total de comparaisons devient approximativement « n + (n-1) + (n-2) + ... + 1 », ce qui est égal à « n(n+1)/2 », soit O(n^2).

* Meilleur des cas :O(n log n)

Le meilleur des cas se produit lorsque le pivot divise systématiquement le tableau en deux moitiés égales (ou presque égales). Dans cette situation, la profondeur de récursion devient « log n », et à chaque niveau, nous effectuons « n » comparaisons, ce qui donne une complexité temporelle de « O(n log n) ».

* Cas moyen :O(n log n)

En moyenne, Quicksort fonctionne très bien. Lorsque la sélection pivot produit systématiquement des partitions raisonnablement équilibrées, la complexité temporelle est « O(n log n) ». La "moyenne" suppose que l'entrée est ordonnée de manière aléatoire et que la sélection du pivot n'est pas systématiquement mauvaise.

Impact du choix pivot :

Le choix du pivot impacte considérablement les performances de Quicksort. Choisir le premier élément comme pivot est une stratégie naïve et peut conduire au pire des cas dans de nombreuses situations courantes.

Techniques d'atténuation :

Pour éviter le pire des cas lors de l’utilisation du tri rapide, il est crucial de choisir un bon pivot. Voici quelques techniques courantes :

* Pivot aléatoire : Choisir un élément aléatoire comme pivot est un moyen simple et efficace d’éviter le pire des cas. Cela rend les performances de l'algorithme moins dépendantes de l'ordre initial des entrées.

* Médiane sur trois : Choisissez la médiane des premier, milieu et dernier éléments du tableau comme pivot. Cela fournit souvent un meilleur pivot que le simple choix du premier élément.

* Autres stratégies de sélection de pivot : Il existe des stratégies de sélection de pivot plus sophistiquées, mais elles ajoutent souvent des frais généraux qui dépassent leurs avantages pour les cas d'utilisation typiques.

En résumé :

Utiliser le premier élément comme pivot dans Quicksort peut être une mauvaise stratégie, surtout si le tableau d'entrée est susceptible d'être trié ou presque. Il est préférable d'utiliser des stratégies de sélection pivot qui tentent de produire des partitions plus équilibrées pour garantir que l'algorithme fonctionne plus près de sa complexité temporelle moyenne « O(n log n) ».

Article précédent： Quelle est la complexité temporelle de l’algorithme de tri rapide ?
Article suivant： Quelle est la complexité temporelle du tri rapide dans le pire des cas ?