Pourquoi le tri rapide est-il meilleur que les autres algorithmes de tri dans la pratique?

^{Ceci est une rediffusion d'une question sur cs.SE par Janoma . Crédits complets et butin pour lui ou cs.SE.}

Dans un cours d'algorithmes standard, nous apprenons que le tri rapide est O (n log n) en moyenne et O (n²) dans le pire des cas. Dans le même temps, d'autres algorithmes de tri sont étudiés qui sont O (n log n) dans le pire des cas (comme mergesort et heapsort ), et même le temps linéaire dans le meilleur des cas (comme bubbleort ) mais avec des besoins de mémoire supplémentaires.

Après un coup d'œil rapide sur certains temps de fonctionnement supplémentaires, il est naturel de dire que le tri rapide ne devrait pas être aussi efficace que d'autres.

De plus, considérez que les étudiants apprennent dans les cours de programmation de base que la récursivité n'est pas vraiment bonne en général car elle pourrait utiliser trop de mémoire, etc. vraiment bon car c'est un algorithme récursif.

Pourquoi, alors, le tri rapide surpasse-t-il les autres algorithmes de tri dans la pratique? Cela a-t-il à voir avec la structure des données du monde réel ? Cela a-t-il à voir avec le fonctionnement de la mémoire dans les ordinateurs? Je sais que certains souvenirs sont beaucoup plus rapides que d'autres, mais je ne sais pas si c'est la vraie raison de cette performance contre-intuitive (par rapport aux estimations théoriques).

Je ne suis pas d'accord pour dire que le tri rapide est meilleur que les autres algorithmes de tri dans la pratique.

Dans la plupart des cas, Timsort - l'hybride entre le tri par fusion / insertion qui exploite le fait que les données que vous triez commencent souvent par un tri ou un tri inversé.

Le tri rapide le plus simple (pas de pivot aléatoire) traite ce cas potentiellement commun comme O (N ^ 2) (réduit à O (N lg N) avec des pivots aléatoires), tandis que TimSort peut gérer ces cas dans O (N).

Selon ces repères en C # comparant le tri rapide intégré à TimSort, Timsort est nettement plus rapide dans les cas principalement triés, et légèrement plus rapide dans le cas de données aléatoires et TimSort s'améliore si la fonction de comparaison est particulièrement lente. Je n'ai pas répété ces benchmarks et je ne serais pas surpris si quicksort battait légèrement TimSort pour une combinaison de données aléatoires ou s'il y avait quelque chose de bizarre dans le tri intégré de C # (basé sur quicksort) qui le ralentissait. Cependant, TimSort présente des avantages distincts lorsque les données peuvent être partiellement triées et est à peu près égal à quicksort en termes de vitesse lorsque les données ne sont pas partiellement triées.

TimSort a également l'avantage supplémentaire d'être un type stable, contrairement au quicksort. Le seul inconvénient de TimSort utilise la mémoire O (N) par rapport à la mémoire O (lg N) dans l'implémentation (rapide) habituelle.

Le tri rapide est considéré comme plus rapide car le coefficient est plus petit que tout autre algorithme connu. Il n'y a aucune raison ni preuve à cela, juste aucun algorithme avec un coefficient plus petit n'a été trouvé. Il est vrai que d'autres algorithmes ont également un temps O ( n log n ), mais dans le monde réel, le coefficient est également important.

Notez que pour les petites insertions de données, le tri (celui qui est considéré comme O ( n ² )) est plus rapide en raison de la nature des fonctions mathématiques. Cela dépend des coefficients spécifiques qui varient d'une machine à l'autre. (À la fin, seul l'assemblage fonctionne vraiment.) Donc, parfois, un hybride de tri rapide et de tri par insertion est le plus rapide en pratique, je pense.

Quicksort ne surpasse pas tous les autres algorithmes de tri. Par exemple, le tri ascendant de tas ( Wegener 2002 ) surpasse le tri rapide pour des quantités raisonnables de données et est également un algorithme sur place. Il est également facile à mettre en œuvre (au moins, pas plus difficile que certaines variantes optimisées de tri rapide).

Ce n'est pas si connu et vous ne le trouvez pas dans de nombreux manuels, ce qui peut expliquer pourquoi il n'est pas aussi populaire que quicksort.

Vous ne devez pas vous concentrer uniquement sur le pire des cas et uniquement sur la complexité du temps. Il s'agit plus de la moyenne que du pire, et c'est du temps et de l' espace.

Tri rapide:

• a une complexité temporelle moyenne de Θ ( n log n );
• peut être implémenté avec une complexité d'espace de Θ (log n );

Tenez également compte du fait que la grande notation O ne prend en compte aucune constante, mais dans la pratique, cela fait une différence si l'algorithme est quelques fois plus rapide. Θ ( n log n ) signifie que cet algorithme s'exécute dans K  n  log ( n ), où K est constant. Quicksort est l'algorithme de tri par comparaison avec le K le plus bas .

Quicksort est souvent un bon choix car il est raisonnablement rapide et raisonnablement rapide et facile à mettre en œuvre.

Si vous souhaitez sérieusement trier de grandes quantités de données très rapidement, vous êtes probablement mieux avec une certaine variation sur MergeSort. Cela peut être fait pour profiter du stockage externe, peut utiliser plusieurs threads ou même des processus, mais ils ne sont pas triviaux à coder.

Les performances réelles des algorithmes dépendent de la plate-forme, ainsi que du langage, du compilateur, de l'attention du programmeur aux détails de l'implémentation, de l'effort d'optimisation spécifique, etc. Ainsi, "l'avantage factoriel constant" de quicksort n'est pas très bien défini - c'est un jugement subjectif basé sur les outils actuellement disponibles, et une estimation approximative de "l'effort de mise en œuvre équivalent" par quiconque effectue réellement l'étude comparative des performances. .

Cela dit, je pense que le tri rapide fonctionne bien (pour une entrée aléatoire) car il est simple et parce que sa structure récursive est relativement compatible avec le cache. D'un autre côté, parce que son pire cas est facile à déclencher, toute utilisation pratique d'un quicksort devra être plus complexe que ce que sa description de manuel l'indiquerait: ainsi, des versions modifiées comme introsort.

Au fil du temps, à mesure que la plate-forme dominante change, différents algorithmes peuvent gagner ou perdre leur avantage relatif (mal défini). La sagesse conventionnelle sur les performances relatives peut très bien être à la traîne de ce changement, donc si vous n'êtes vraiment pas sûr de l'algorithme le mieux adapté à votre application, vous devez implémenter les deux et les tester.