Pourquoi quicksort est plus populaire que radix tri?

Question

Pourquoi quicksort (ou introsort), ou tout algorithme de tri par comparaison est plus fréquent que radix tri? Surtout pour les numéros de tri.

Radix-tri n'est pas en fonction de comparaison, peut donc être plus rapide que O (n logn). En fait, il est O (k n), où k est le nombre de bits utilisés pour représenter chaque élément. Et la surcharge de la mémoire n'est pas critique, puisque vous pouvez choisir le nombre de seaux à utiliser, et la mémoire nécessaire peut être inférieure aux exigences de mergesort.

-t-il à voir avec la mise en cache? Ou peut-être accéder à des octets aléatoires d'entiers dans le tableau?

Answer 1

Deux arguments viennent à l'esprit:

1. Quicksort / introsort est plus souple:

   travail Quicksort et introsort bien avec toutes sortes de données. Tout ce que vous avez besoin pour le tri est la possibilité de comparer les articles. Ceci est trivial avec des chiffres, mais vous pouvez trier les autres données aussi bien.

   trier Radix d'autre part trie simplement les choses par leur représentation binaire. Il compare jamais les éléments les uns contre les autres.

2. Radix a besoin de plus de mémoire de tri.

   Toutes les implémentations de tri radix que je l'ai utilisé un tampon secondaire vu pour stocker les résultats de tri partiels. Cela augmente les besoins en mémoire de l'algorithme de tri. Cela peut ne pas être un problème si vous ne sorte quelques kilo-octets, mais si vous allez dans la gamme de giga-octets, il fait une énorme différence.

   Si je me souviens bien en place un algorithme de exist tri radix sur papier bien.

Answer 2

Une réponse évidente est que vous pouvez types sorte arbitraires à l'aide quicksort (c.-à-tout ce qui est comparable), alors que vous êtes limité à des chiffres uniquement avec radix. Et est l'OMI quicksort beaucoup plus intuitive.

Answer 3

Radix est un peu plus lent pour (la plupart) des cas d'utilisation du monde réel.

L'une des raisons est la complexité de l'algorithme:

Si des éléments sont uniques, k> = log (n). Même avec des éléments en double, l'ensemble des problèmes où k

Une autre est la mise en œuvre:

L'exigence de mémoire supplémentaire (qui lui-même est un inconvénient), affecte les performances du cache négativement.

Je pense qu'il est sûr de dire que de nombreuses bibliothèques, comme la bibliothèque standard, utilisez Quicksort parce qu'il fonctionne mieux dans la majorité des cas. Je ne pense pas que « la mise en œuvre difficile » ou « moins intuitive » sont les principaux facteurs.

Answer 4

Comme mentionné sur Wikipedia

  

Le thème de l'efficacité par rapport à radix sorte d'autres algorithmes de tri est un peu délicat et sujet à beaucoup de malentendus. Que ce soit radix est un peu tout aussi efficace, moins efficace ou plus efficace que les meilleurs algorithmes basés comparaison dépend des détails des hypothèses. l'efficacité de tri est Radix O (d · n) pour les touches n qui ont des chiffres d ou moins. Parfois, d est présenté comme une constante, ce qui rendrait radix sorte mieux (pour n suffisamment grand) que les meilleurs algorithmes de tri à base de comparaison, qui sont tous O (n · log (n)) nombre de comparaisons nécessaires. Cependant, en général d ne peut pas être considérée comme une constante. En particulier, sous la commune (mais parfois implicite) hypothèse que toutes les clés sont distinctes, alors d doit être au moins de l'ordre de log (n), ce qui donne au mieux (avec les touches denses) une complexité temps O (n · log (n)) . Cela semble faire au plus radix sorte aussi efficace que les meilleures sortes à base de comparaison (et pire encore si les clés sont beaucoup plus longues que log (n)).

     

L'argument contre est les algorithmes basés comparaison sont mesurés en nombre de comparaisons, pas la complexité du temps réel. Dans certaines hypothèses, les comparaisons seront en moyenne constante de temps, sous d'autres, ils ne seront pas. Les comparaisons de clés générées aléatoirement prend du temps constant en moyenne, en tant que clés diffèrent sur le premier bit dans la moitié des cas, et diffèrent sur le second bit dans la moitié de la moitié restante, et ainsi de suite, aboutissant à une moyenne de deux bits qui doivent être comparés. Dans un algorithme de tri les premières comparaisons faites satisfait à la condition de hasard, mais comme le genre progresse, les clés comparées sont clairement pas choisis au hasard plus. Par exemple, envisager une sorte de fusion ascendante. La première passe comparera paires de clés aléatoires, mais la dernière passe comparera les clés qui sont très proches dans l'ordre de tri.

     

Le facteur décisif est de savoir comment les clés sont distribuées. Le meilleur des cas pour le tri radix est qu'ils sont considérés comme des modèles de bits consécutifs. Cela rendra les clés aussi courte qu'ils peuvent être, en supposant encore ils sont distincts. Cela rend le tri par base O (n · log (n)), mais les types à base de comparaison ne seront pas aussi efficaces, les comparaisons ne seront pas constante de temps dans cette hypothèse. Si l'on place supposons que les clés sont des motifs de bits de longueur k · log (n) pour une k constante> 1 et base 2 log, et qu'ils sont uniformément au hasard, puis trier radix sera toujours O (n · log (n) ), mais ce sera le genre à base de comparaison, la longueur « extra » fait même les touches qui sont consécutives dans le résultat assez différent Sorted que les comparaisons sont constante de temps en moyenne. Si les touches sont plus longues que O (log (n)), mais au hasard, puis triera radix être inférieur. Il y a beaucoup d'autres hypothèses qui peuvent être faites aussi bien, et la plupart exigent une étude minutieuse de faire une comparaison correcte.

Answer 5

Points faits dans d'autres réponses sont valables, mais pour autant que la préoccupation de la vôtre mentionnées dans plusieurs commentaires

  

... le fait que les algorithmes de tri par défaut pour les numéros sont mis en œuvre à l'aide quicksort. En particulier, les mises en œuvre dans les bibliothèques ...

Quicksort est le choix 'sûr'. Le moteur d'exécution potentiel d'une sorte radix basé sur une sorte de comptage est très attrayant, oui, mais radix est un peu subsceptible d'effectuer mal sur des jeux de données malveillants / malheureux. Si le nombre de chiffres des touches triées approche du nombre de clés à trier, trier radix se produit sur n ^ 2 avec une complexité spatiale non négligeable, et il a tendance à avoir BUILTIN assez élevé des constantes d'exécution autres que celle du nombre des chiffres des clés étant trié.
Mergesort est attrayante parce que son comportement est, à certains égards, à un quicksort analogue qui capte un pivot optimal à chaque occasion (la médiane). Cependant, il est livré avec une complexité de l'espace appréciable. Il est pas subsceptible aux données malicieuses / malheureux que Radix, mais aussi n'offre pas l'exécution possible attrayante. A base tri rapide fonctionne très bien sur la plupart des jeux de données, à l'exception près (ou totalement) triées ceux, et est livré avec une petite complexité de l'espace.
La vulnérabilité de Quicksort est facilement traitée en le convertissant en un quicksort aléatoire. La vulnérabilité de sorte Radix est résolu en plaçant des restrictions sur les touches triées, qui par nature limiter les utilisateurs de la bibliothèque. Quicksort est plus performant que la fusion sur les petits ensembles de données et effectue raisonnablement lorsque la fusion pourrait être plus rapide.
Lors de la mise en œuvre d'une bibliothèque, vous voulez faire génériquement utile. Prenez ces exemples, une application web et un petit appareil avec un microcontrôleur extrêmement restreint. Les applications Web doivent traiter des données malveillantes sur une base régulière, et ont également une grande variété de besoins. Une bibliothèque avec des restrictions préconditionnés est moins susceptible d'être utile. Dans le cas du micro-contrôleur, il peut être limité restrictivement l'espace et incapable de renoncer à la moindre où l'on peut être sauvé. Quicksort économise de l'espace, et complétera seulement plus lent par un multiplicateur constant si une situation qui est plus lente.
En somme -
1.) Les bibliothèques sont souvent codées pour autant la facilité d'utilisation générique que possible
2.) Bonne performance tout autour est acceptable, surtout si elle est dans de nombreux cas, la meilleure performance
3.) L'espace est pas toujours une question primordiale, mais quand il est, il est souvent explicitement si restrictivement

Answer 6

efficacité de sorte Radix = O (c.n) où c = nombre le plus élevé de chiffres parmi l'ensemble de touche d'entrée. n = nombre de clés de jeu de touche d'entrée.

= O meilleur des cas de tri rapide (n. Log n) où n = nombre de clés de jeu de touche d'entrée.

Supposons 16 nombres à trier avec 6 chiffres chacun:

Radix = sort 16 * 6 = 96 unités de temps. tri rapide = 16 * 4 = 64 unités de temps.

Leçon: Quand « c » est moins, Radix ne gagne. Quand il est élevé, il perd. tri rapide est indépendant du nombre de chiffres dans une clé et qui le rend un peu mieux et plus pratique acceptable