Quel algorithme de tri fonctionne le mieux sur un très grand ensemble de données

Question

Je cherchais sur Internet pour trouver quel algorithme de tri convient le mieux pour un très grand ensemble de données. J'ai trouvé que beaucoup ont une opinion que le tri par fusion est le meilleur car il est juste, et qu'il garantit que la complexité du temps est O (n log n) et le tri rapide n'est pas sûr: Il est aussi vrai que les variations du quicksort peuvent aussi ne soyez pas en sécurité car le jeu de données réel peut être n'importe quoi.

Si l'échange de deux éléments a un coût en temps négligeable, alors pourquoi ne pas choisir le tri de tas comme meilleur algorithme de tri dans ce cas car il est en place ainsi que O (n log n)?

En cas de tri par fusion, il faut un autre espace O (n); Si les données sont très grandes, nous ne pouvons pas utiliser cet algorithme.

Se il vous plaît dites-moi: quel algorithme devrait être le meilleur dans ce scénario?

Answer 1

Il n'y a pas un seul algorithme qui soit clairement le meilleur algorithme. Cela dépend d'un tas de facteurs.

Pour commencer, pouvez-vous adapter vos données dans la mémoire principale? Si vous ne le pouvez pas, vous devez utiliser un algorithme de tri externe. Ces algorithmes sont souvent basés sur quicksort et mergesort. Deuxièmement, savez-vous quelque chose au sujet de votre distribution d'entrée? Si c'est principalement trié, alors quelque chose comme Timsort peut être une excellente option, car il est conçu pour fonctionner correctement sur les données triées. Si c'est plutôt aléatoire, Timsort n'est probablement pas un bon choix.

Troisièmement, quels types d'éléments triez-vous? Si vous triez des objets génériques, vous êtes à peu près limité au tri par comparaison. Sinon, vous pourriez peut-être utiliser un tri sans comparaison comme le tri par comptage ou le tri radix.

Quatrièmement, combien de noyaux avez-vous? Certains algorithmes de tri (quicksort, mergesort, tri de base MSD) se mettent en parallèle très bien, alors que d'autres ne le font pas (heapsort).

Cinquièmement, comment vos données sont-elles représentées? Si elles sont stockées dans un tableau, quicksort ou une variante de quicksort fera probablement bien à cause de la localité de référence, tandis que mergesort pourrait être lent en raison de la mémoire supplémentaire nécessaire. S'ils sont dans une liste chaînée, cependant, la localité de référence de quicksort disparaît et mergesort redevient soudain compétitif. La meilleure option est probablement de prendre en compte un grand nombre de facteurs différents, puis de prendre une décision à partir de là. Une des raisons pour lesquelles il est si amusant de concevoir et d'étudier des algorithmes est qu'il y a rarement un seul meilleur choix; Souvent, la meilleure option dépend d'une tonne sur votre situation particulière et des changements basés sur ce que vous voyez.

(Vous avez mentionné quelques détails sur quicksort, heapsort et mergesort que je voulais aborder avant de conclure cette réponse. Alors que vous avez raison que quicksort a un O dégénéré (n) pire des cas, il L'algorithme introsort garde trace de la profondeur de récursivité et fait passer l'algorithme à heapsort s'il semble que le quicksort dégénère, ce qui garantit O (n log n) pire comportement avec un minimum de mémoire et maximise le quicksort randomisé, tout en ayant un O (n) pire cas, a une probabilité infinitésimale de toucher réellement ce pire des cas

Heapsort est un bon algorithme en pratique, mais n'est pas aussi rapide que les autres algorithmes dans certains cas car il n'a pas une bonne localisation de référence. Cela dit, le fait qu'il ne dégénère jamais et n'a besoin que de l'espace auxiliaire O (1) est un énorme argument de vente.

Mergesort a besoin de beaucoup de mémoire auxiliaire, ce qui est une des raisons pour lesquelles vous ne voudrez peut-être pas l'utiliser si vous avez besoin de beaucoup de données à trier. Cela vaut la peine de le savoir, car ses variantes sont largement utilisées.)

Answer 2

Votre question est trop ouverte pour qu'on y réponde spécifiquement. Il existe un certain nombre d'algorithmes de tri efficaces et chacun a ses propres forces et faiblesses. Si vous connaissez vos données, il est possible qu'un algorithme d'efficacité optimale (heap, quick, merge, etc.) ne soit pas le bon outil pour le travail. Par exemple, dans un produit récent, nous devions conserver les signets dans un document Word trié par ordre d'apparition. Les signets pouvaient devenir non triés en raison de l'édition du document (copier, couper, coller) donc après chacune de ces opérations, il était important de recourir à la liste. Dans ce cas, bubblesort était la bonne réponse même si elle a une plus grande complexité en O, puis un nombre quelconque d'autres algorithmes. Le fait que le tri soit efficace lorsque la liste est presque triée (ce qui est généralement le cas dans cette situation) et qu'il s'agit d'une opération sur place signifiait que c'était le bon outil pour le travail. Jetez un coup d'œil à vos données et lisez les différentes forces et faiblesses des algorithmes de tri bien connus et vous serez sur la bonne voie pour répondre à votre propre question.