Bucket sort und radix sort sind enge Cousins; Bucket-Sortierung geht von MSD zu LSD, während Radix-Sortierung in beide "Richtungen" (LSD oder MSD) gehen kann. Wie funktionieren beide Algorithmen und insbesondere wie unterscheiden sie sich?Was ist der Unterschied zwischen Bucket-Sortierung und Radix-Sortierung?
Der erste Durchlauf von RadixSort und BucketSort ist genau gleich. Die Elemente werden in buckets (oder bins) von inkrementellen Bereichen (z. B. 0-10, 11-20, ... 90-100) gesetzt, abhängig von der Anzahl der Stellen in der größten Anzahl.
Im nächsten Durchlauf werden diese "Buckets" jedoch durch BucketSort geordnet und an ein Array angehängt. RadixSort hängt jedoch die Buckets an, ohne sie weiter zu sortieren, und ordnet sie basierend auf der zweiten Ziffer (dem Platz der Zehner) der Nummern neu. Daher ist BucketSort effizienter für 'Dichte' Arrays, während RadixSort mit spärlichen (gut, nicht genau spärlich, aber räumlich getrennt) Arrays umgehen kann.
Bucket Sort und Radix Sort sind wie Schwestersortieralgorithmen, da sie keine Vergleichssorten sind und die allgemeine Idee ähnlich ist. Außerdem sind beide in der Implementierung ein wenig abstrakt.
Radix Sort:
Radix bedeutet Basis (binär, oktale, dezimale, etc). Daher ist diese Sortierung für Zahlen (auch für Strings). Dies funktioniert, wenn jedes Element E wie e k ... e e e , wobei e i in einem gewissen Bereich liegt. (In der Regel 0 bis eine Base, wie 0-9 dezimal oder 0-255 in ASCII-Zeichen)
Es verwendet dann k Durchgänge eines stabilen Untersortieralgorithmus (Es muss stabil seine Art oder auch Radix gewonnen arbeite nicht) um die Nummern zu sortieren. Dieser Untersortieralgorithmus ist in der Regel auch das Zählen von Sortier- oder Bucket-Sortierungen, aber kann nicht von Radix selbst sortiert werden..
Sie können von Most Significant Digit oder Least Significant Digit gestartet werden, da es jede Zahl in jedem Durchgang (0 oder 0 bis k aus k)
Es ist ein stabil Sortieralgorithmus schlurft.
Bucketsort:
Er trennt Array in kleinere Gruppen oder Eimern und sortiert sie einzeln einen Untersortieralgorithmus oder rekursiven Aufruf an sich selbst und anschließend kombiniert das Ergebnis. Zum Beispiel, Sortieren von Spielern durch Hinzufügen in Eimer ihres Teams, dann sortieren sie nach ihren Trikot-Nummern oder etwas wie Sortieren von Zahlen von 1-30 in 3 Eimern von 1-10, 11-20, 21-30.
Der Kombinationsschritt ist trivial (im Gegensatz zu merge sort).einfach kopieren Elemente jeden Eimer wieder in ursprüngliche Anordnung oder den Kopf jeder Schaufel verbindet mit Schwanz früherer bucket (im Fall von verketteten Listen)
Radix/base ein Typ/Beispiel der Gruppe/Eimer sein könnte beim Sortieren von Zahlen. Daher könnten Sie von MSD radix denken als ein modifiziertes Beispiel von Bucketsort
Bucket Sortierung ist nicht an Ort und Stelle aber stabil Algorithmus sortiert. Allerdings könnten einige Variationen von Bucketsort nicht stabil sein (wenn Sie einen Teilsortieralgorithmus verwendet werden, die nicht stabil ist)
einige gute Vergleiche :) –
Könnten Sie diese Antwort erweitern, um zu erklären, warum die Zeit Komplexität dieser beiden Methoden unterschiedlich sind? h. warum ist Bucket-Sortierung O (n + k), aber Radix-Sortierung ist O (nk) & agr; –
@ShaunBudhram Es ist alte Frage, aber wenn jemand dies liest will es wissen. Aus der Beschreibung geht hervor, dass Bucket-Sortierung an N weitergegeben wird und dann K-Buckets zusammenführt (Reihenfolge innerhalb des Buckets ist beliebig). Während radix sort einen Durchlauf für jeden Bucket durchführt, denke ich hier, dass das Sortieren von Strings ein besseres Beispiel wäre, also machen Sie K-Pässe mit der Komplexität N. –
Was meinen Sie mit "BucketSort bestellt diese 'Buckets'"? Ist jeder Eimer mit einem anderen Algorithmus sortiert oder was? Weil jeder Bucket nicht vollständig sortiert ist, wenn Sie nach 10s gruppieren. – mpen