Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

Le tri rapide est assez similaire au tri par fusion dans le sens où cet algorithme aide les programmeurs à diviser pour mieux régner. Il choisit des éléments comme pivot, après quoi il crée des partitions dans le tableau. Le tri rapide a de nombreuses versions et chacune d’entre elles choisit le pivot différemment.

La commande partition() est sans doute la partie la plus importante du tri rapide. Les cibles de partition reçoivent un tableau avec un élément de tableau x comme pivot. Vous devez placer le x à la bonne position, qui est le tableau trié, qui sera suivi par le placement d’éléments plus petits que x avant lui. Enfin, vous devez placer les éléments plus grands que x après lui. Assurez-vous de faire tout cela en temps linéaire.

Il convient également de garder à l’esprit que le tri rapide crée des partitions dans les tableaux, après quoi il s’appelle lui-même deux fois en répétition pour trier les sous-réseaux qui en résultent. Un algorithme comme celui-ci s’avère incroyablement pratique pour les grands ensembles de données. En effet, O(n2) sont ses complexités dans le pire des cas. Les deux termes initiaux sont là pour les appels récursifs, tandis que le dernier terme est utile dans le processus de partition. Les éléments plus petits que le pivot sont représentés par k.

Le temps que prend le tri rapide dépend généralement de la stratégie de partition, ainsi que du tableau d’entrée.

Les trois cas du tri rapide

Comme divers autres algorithmes de tri, le tri rapide a également des cas de figure. Voyons-les ci-dessous :

Le pire des cas

Ce type de cas se produit lorsque le processus de partition choisit l’élément le plus petit ou le plus grand comme pivot. Si l’on considère la stratégie de partition discutée précédemment, où le dernier élément est choisi comme pivot à chaque fois, le scénario du pire endroit finira par se produire une fois que le tableau sera trié en ordre décroissant ou croissant. La récurrence pour le pire cas est la suivante :

T(n) = T(0) + T(n-1) + (n)ce qui est équivalent à T(n) = T(n-1) + (n)

Meilleur cas

Le meilleur cas se produit lorsque le processus de partition choisit l’élément du milieu comme pivot. La récurrence pour le meilleur cas est la suivante :

T(n) = 2T(n/2) + (n)

Cas moyen

Il faut considérer chaque permutation de tableau et calculer le temps que prend chaque permutation pour effectuer une analyse de cas. Bien sûr, ce processus peut être assez compliqué, même pour les programmeurs expérimentés. Cela dit, la prise en compte du cas où la partition place O(n/9) avec O(9n/10) éléments peut vous donner une estimation du cas moyen. La récurrence de ce cas est la suivante.

T(n) = T(n/9) + T(9n/10) + (n)

Questions courantes posées sur le tri rapide

Bien que de nombreuses questions soient posées sur le tri rapide, celles mentionnées ci-dessous sont sans doute les plus courantes :

Le tri rapide est-il un algorithme stable ?

Eh bien, l’implémentation par défaut du tri rapide n’est pas stable. Cela dit, il est possible d’ajouter de la stabilité aux algorithmes de tri en considérant l’indice comme un paramètre de comparaison.

Qu’est-ce que le tri rapide à trois voies ?

Lorsqu’il est question d’un algorithme de tri rapide ordinaire, nous choisissons un élément pour servir de pivot, nous créons une partition dans le tableau. Ensuite, nous récurons les sous-réseaux présents sur les côtés droit et gauche du pivot.

Le Tri rapide est-il un algorithme in-place ?

Selon la définition large de l’algorithme in-place, le tri rapide peut effectivement être considéré comme ce type d’algorithme de tri. En effet, il utilise de l’espace supplémentaire pour stocker les appels de fonctions récursives. Cependant, il ne manipule pas l’entrée de quelque manière que ce soit.

Plus rapide que la plupart des algorithmes de tri

Bien qu’il soit indéniable que la complexité temporelle du tri rapide dans le pire des cas est O(n2), plus que le tri par tas, le tri par fusion et de nombreux autres algorithmes de tri, le tri rapide est incroyablement rapide. L’une des raisons en est que vous pouvez implémenter efficacement sa boucle interne dans plusieurs types de données et d’architectures du monde réel.
Qui plus est, vous pouvez mettre en œuvre le tri rapide de diverses manières, simplement en modifiant le choix du pivot. Ce faisant, vous minimisez l’occurrence du pire cas pour tout type de données. Cela dit, les programmeurs préfèrent généralement utiliser le tri par fusion lorsqu’il y a trop de données, surtout si elles se trouvent dans un stockage externe.

Qu’en est-il de l’utilisation du tri rapide dans les listes liées?

Lorsqu’il s’agit de listes liées, les choses sont assez différentes en raison des différences présentes dans l’allocation de la mémoire du tableau. Les nœuds des listes liées sont très différents des tableaux et ne sont souvent pas adjacents dans la mémoire. De plus, les listes liées vous permettent d’entrer des éléments au centre, ce qui n’est pas possible dans un tableau. Dans de tels scénarios, les programmeurs préfèrent utiliser le tri par fusion car il s’avère être une option plus viable que le tri rapide.

Pourquoi les programmeurs préfèrent le tri rapide pour trier les tableaux

À la base, le tri rapide est un simple tri in-place, ce qui signifie qu’il ne nécessite pas de stockage supplémentaire. En revanche, le tri par fusion nécessite O(N) de stockage supplémentaire. Pour ceux qui se posent la question, le N désigne la taille du tableau, qui peut être incroyablement vaste. La désallocation et l’allocation de l’espace supplémentaire requis pour le tri par fusion augmentent le temps d’exécution de l’algorithme.

Une fois que nous comparons la complexité moyenne, il est facile de voir que la complexité moyenne des deux types de tri est O(NlogN). Cependant, leurs constantes ont tendance à différer. Lorsqu’il s’agit de tableaux, le tri par fusion ne réussit pas car il utilise O(N) d’espace de stockage supplémentaire. Les implémentations les plus pratiques du tri rapide utilisent la version aléatoire. La complexité temporelle moyenne de cette version est de O(nLogn). Il faut également garder à l’esprit qu’il existe une possibilité de pire cas avec la version randomisée. Cependant, cela n’apparaît pas pour des modèles spécifiques tels que les tableaux triés.

L’algorithme de tri rapide est assez convivial pour le cache en raison de son excellente localité de référence, en particulier lorsqu’il est utilisé pour des tableaux. De plus, le tri rapide est également récursif en queue, ce qui signifie que vous devez effectuer des optimisations d’appel de queue.