Warum ist quicksort populärer als Radix-Art?

Question

Warum quicksort (oder Introsort) oder eine vergleichsbasierten Sortieralgorithmus häufiger als Radix-Art ist? Speziell für Zahlen zu sortieren.

Radix-Sortierung ist nicht Vergleich basiert, daher schneller sein kann als O (n logn). In der Tat ist es O (k n), wobei k die Anzahl von Bits verwendet wird, ist jedes Element zu repräsentieren. Und der Speicher-Overhead ist nicht kritisch, da die Anzahl der Schaufeln zu verwenden wählen können, und erforderliche Speicher kann kleiner sein als mergesort Anforderungen.

Hat es mit Caching zu tun? Oder vielleicht zufälliges Bytes von ganzen Zahlen im Array zugreifen?

Answer 1

Zwei Argumente kommen mir in den Sinn:

1. Quicksort / Introsort ist flexibler:

   Quicksort und Introsort Arbeit gut mit allen Arten von Daten. Alles, was Sie für die Sortierung müssen, ist die Möglichkeit, Produkte zu vergleichen. Dies ist trivial mit Zahlen, aber Sie können sortieren andere Daten als auch.

   Radix Art auf der anderen Seite sortiert die Dinge nur durch ihre binäre Darstellung. Es vergleicht niemals Gegenstände gegeneinander.

2. Radix braucht Art mehr Speicher.

   All Radixsort Implementierungen, dass ich Verwendung einen sekundären Puffer teilweise Sortierung speichern Ergebnisse gesehen habe. Dadurch erhöht sich die Speicheranforderungen des Sortieralgorithmus. Das kann kein Problem sein, wenn Sie Art ein paar Kilobyte, aber wenn Sie den Gigabyte-Bereich gehen in sie einen großen Unterschied macht.

   Wenn ich Recht einen an Ort und Stelle Radix-Sortieralgorithmus exist auf Papier erinnern though.

Answer 2

Eine offensichtliche Antwort ist, dass Sie sortieren beliebige Typen mit quicksort (dh alles, was vergleichbar ist), während Sie auf Zahlen beschränkt sind, nur mit Radix. Und IMO quicksort ist viel intuitiver.

Answer 3

Radix Art ist langsamer für die (meisten) reale Welt Anwendungsfälle.

Ein Grund dafür ist die Komplexität des Algorithmus:

Wenn Elemente eindeutig sind, k> = log (n). Auch mit doppelten Elemente, ist die Menge von Problemen, bei denen k

Ein weiterer Grund ist die Umsetzung:

Der zusätzliche Speicherbedarf (die in ihm selbst ein Nachteil ist), wirkt sich negativ auf die Leistung Cache.

Ich denke, es ist sicher, dass viele Bibliotheken zu sagen, wie die Standard-Bibliothek verwenden Quicksort, weil sie eine bessere Leistung in der Mehrzahl der Fälle. Ich glaube nicht, dass diese „schwierige Umsetzung“ oder „weniger intuitiv“ sind wichtige Faktoren.

Answer 4

Wie bereits erwähnt auf Wikipedia

  

Das Thema der Effizienz der Radixsort im Vergleich zu anderen Sortieralgorithmen ist etwas schwierig und unterliegt einer ziemlich viele Missverständnisse. Ob Radixsort ist ebenso effizient, weniger effizient oder effizienter als die besten vergleichsbasierten Algorithmen hängt von den Einzelheiten der getroffenen Annahmen. Radix Sortiereffizienz ist O (d · n) für n Tasten, die d oder weniger Stellen aufweisen. Manchmal d wird als Konstante präsentiert, die Radixsort besser machen würde (für hinreichend große n) als die besten vergleichsbasierten Sortieralgorithmen, die alle O (n · log (n)) Anzahl der Vergleiche benötigt. Jedoch kann im allgemeinen d keine Konstante angesehen werden. Insbesondere im Rahmen der gemeinsamen (aber manchmal implizite) Annahme, dass alle Schlüssel verschieden sind, dann d zumindest in der Größenordnung von log sein muss (n), die im besten Fall gibt (mit dicht gepackten Tasten), um eine Zeitkomplexität O (n · log (n)) . Das scheint Radixsort höchstens genauso effizient wie die besten vergleichsbasierten Sorten zu machen (und noch schlimmer, wenn Tasten sind viel länger als log (n)).

     

Das Gegenargument ist die vergleichsbasierten Algorithmen in der Anzahl der Vergleiche gemessen werden, nicht unbedingt die Zeitkomplexität. Unter bestimmten Annahmen werden die Vergleiche konstante Zeit im Durchschnitt sein, unter anderem werden sie nicht. Vergleiche der zufällig erzeugten Schlüssel benötigt konstante Zeit im Durchschnitt als Schlüssel am ersten Bit unterscheiden sich in der Hälfte der Fälle, und unterscheiden sich auf der zweiten Bit in der Hälfte der verbleibenden Hälfte, und so weiter, in einem Durchschnitt von zwei Bits führt, daß müssen verglichen werden. In einem Sortieralgorithmus die ersten Vergleiche erfüllt die Zufälligkeit Zustand, aber die Art, wie die Schlüssel fortschreitet verglichen werden mehr eindeutig nicht zufällig ausgewählt. Betrachten wir zum Beispiel einen Bottom-up-Mergesort. Der erste Durchgang wird Paare Zufallsschlüssel vergleichen, aber der letzte Pass vergleicht die Tasten, die ganz in der Nähe in der Sortierreihenfolge sind.

     

Der entscheidende Faktor ist, wie die Tasten verteilt sind. Der beste Fall für Radixsort ist, dass sie als aufeinanderfolgende Bitmuster getroffen werden. Dadurch werden die Tasten so kurz machen wie sie sein können, noch verschieden sie sind unter der Annahme. Dies macht Radixsort O (n · log (n)), aber der Vergleich basiert Sorten nicht so effizient sein, da die Vergleiche nicht konstante Zeit unter dieser Annahme wird. Wenn wir stattdessen davon aus, dass die Schlüssel Bitmuster der Länge k · log (n) für eine Konstante k> 1 und Base 2 log, und dass sie gleichmäßig zufällig sind, dann sortieren radix wird immer noch O (n · log (n) ), sondern werden so die Grundlage der Vergleich Art, wie die „extra“ Länge sogar die Schlüssel macht, die in der sortierten Folge aufeinander folgend sind unterschiedlich genug, dass vergleichen konstante Zeit im Durchschnitt ist. Wenn Tasten länger als O (log (n)), aber gelegentlich, dann wird Radixsort minderwertig sein. Es gibt viele andere Annahmen, die auch gemacht werden können, und die meisten erfordern eine sorgfältige Studie ein machen korrekter Vergleich.

Answer 5

gemacht Punkte in anderen Antworten sind gültig, aber so weit wie die Anliegen von Ihnen in mehreren Kommentaren erwähnten

  

... die Tatsache, dass die Standard-Algorithmen für Zahlen Sortierung verwenden quicksort implementiert. Vor allem der Implementierungen in Bibliotheken ...

Quicksort ist die 'sichere' Wahl. Das Potential der Laufzeit eines Radixsort auf einem Countingsort basiert ist sehr attraktiv, ja, aber Radix ist eine Art subsceptible schlecht auf böswillige / unglücklichen Datensätze durchführen. Wenn die Anzahl der Stellen des Schlüssels sortiert werden, um die Anzahl der Schlüssel Ansätze sortiert werden, Radixsort führt an n ^ 2 zusammen mit einer nicht zu vernachlässigender Platzkomplexität, und es neigt dazu, ziemlich hohe builtin Laufzeitkonstanten andere als die von der Anzahl zu haben, die Stellen des Schlüssels sortiert werden.
Mergesort ist attraktiv, weil sein Verhalten ist, in gewisser Weise analog zu einem quicksort, die eine optimale Dreh bei jeder Gelegenheit nimmt (der Median). Allerdings kommt es mit einer nennenswerten Raum Komplexität. Es ist nicht so subsceptible auf bösartige / unglückliche Daten als radix, sondern bietet auch nicht die attraktive möglich Laufzeit. Eine grundlegende quicksort führt sehr gut auf den meisten Datensätze außer fast (oder vollständig) sortierten Einsen, und kommt mit einer winzigen Raum Komplexität.
Quicksort Verwundbarkeit wird leicht behandelt, indem es einer randomisierten quicksort umwandelt. Radixsort Verwundbarkeit ist, indem Beschränkungen für die Tasten gelöst sortiert werden, die von Natur aus der Bibliothek Benutzer einschränken würde. Quicksort ist performanter als merge auf kleine Datenmengen und führt vernünftig, wenn merge könnte schneller sein.
Wenn eine Bibliothek, die, wollen Sie es allgemein nützlich machen. Nehmen Sie diese Beispiele, eine Web-Anwendung und ein kleines Gerät mit einem extrem eingeschränkt Mikrocontroller. Web-Anwendungen müssen mit bösartigen Daten auf einer regelmäßigen Basis beschäftigen, und auch eine Vielzahl von Anforderungen haben. Eine Bibliothek mit vorkonditioniert Einschränkungen ist es weniger wahrscheinlich, nützlich zu sein. Im Falle des Mikrocontrollers kann es eng auf Platz begrenzt und nicht in der Lage den geringsten zu verzichten, wo man gerettet werden kann. Quicksort spart Platz und wird nur langsamer durch einen konstanten Multiplikator abgeschlossen, wenn eine Situation entsteht, dass es langsamer ist.
In Summe -
1.) Bibliotheken sind oft so viel generische Verwendbarkeit wie möglich
kodiert 2.) Gute Leistung rundum ist akzeptabel, vor allem, wenn es in vielen Fällen, die beste Leistung
3.) Der Raum ist nicht immer ein Hauptproblem, aber wenn es ist, ist es oft explizit restriktiv so

Answer 6

Radixsort Effizienz = O (C.n) wobei c = höchste Anzahl von Stellen unter dem Eingangsschlüsselsatz. n = Anzahl der Tasten in dem Eingabetastensatz.

Kurze Art bester Fall = O (n. Log n) wobei n = Anzahl der Schlüssel in dem Eingangsschlüsselsatz.

Angenommen

16 Nummern sortiert werden mit je 6 Stellen:

Radix = sortieren 16 * 6 = 96 Zeiteinheiten. Schnell sort = 16 * 4 = 64 Zeiteinheiten.

Lektion: Wenn ‚c‘ weniger ist, wird Radix gewinnen. Wenn es hoch ist, verliert es. Quicksort ist unabhängig von Anzahl der Stellen in einem Schlüssel und das macht es etwas besser und praktisch akzeptabel