MSD vs LSD Radix Sortieren

Question

Ich lese das Folgende in crls :

Ich verstehe den Text nicht in Gelb.Warum funktionierte radix sort nicht so gut, wenn wir nach ihrer bedeutendsten Ziffer sortieren?Auf welche zusätzlichen "Kartenstapel" bezieht sich?

Vielleicht kann ich dem Beispiel nicht mit Karten folgen, und ein Beispiel mit der tatsächlichen Anzahl wäre am besten.

---

Falls es hilft, sortiert naiv von MSD Doe nicht zu arbeiten, selbst wenn alle Werte d-stellige Nummern sind:

generasacodicetagpre.

wobei (i) das Ergebnis des Sortierens der vorherigen Spalte durch die ith-höchste Ziffer ist.

Answer 1

Es würde funktionieren, das einzige Problem ist, dass es viele zusätzliche Stapel für die schwierigen Zwischenergebnisse erzeugt, die schwer zu verfolgen sind.

Wenn der Sortieralgorithmus den $ D $ -Digit-Nummern sortiert, beginnend mit ihrer signifikantesten Ziffer würde er zunächst 10 Pfähle erstellen (ein Stapel für die Zahlen, die mit beginnen 0, ein anderer für diejenigen, die mit 1 und so weiter beginnen) und dann jeden Hörer rekursiv wie im Buch erklärt sortieren.

Das Problem ist, dass er zum Sortieren des Haufens der Nummern mit 0 der Algorithmus, um zehn weitere Pfähle zu erstellen (einer für die Zahlen, die mit 00 beginnend mit 00 beginnen, der zweite für die mit 01 beginnenden Nummern usw. die Zahlen, die mit 09 beginnen).

So haben wir bisher 19 Pfähle geschaffen. Um den Haufen der Zahlen zu sortieren, beginnend mit 00, müssen wir 10 weitere Pfähle erstellen. Wenn dieser Prozess fortgesetzt wird, bis der $ D $ eine Ziffer sortiert ist, können Sie sich vorstellen, dass eine große Anzahl von Pfählen erstellt wird (wie viele?).

Dies sind die zusätzlichen Pfähle, auf die sich das Buch bezieht.

Wenn Sie LSD Radix-Sort verwenden, müssen Sie die Zahlen nicht überhaupt nicht aufteilen. Sie können den Eingangspapier einfach durch die letzte Ziffer sortieren, dann den gleichen Stapel von der vorletzten Ziffer usw., nachdem Sie nach $ D $ Schritte mit dem erwarteten Ergebnis enden .

Die Intuition ist folgendes: Lassen Sie $ D $ Seien Sie $ 2 $ und lassen Sie $ 83 $ , $ 19 $ und $ 17 $ Seien Sie der Eingang. Der erste Schritt auf MSD-Radix-Sortierung wird $ 17 $ und $ 19 $ vor $ 83 $ . Wenn Sie dann den gleichen ganzen Stapel von der zweiten Ziffer sortieren, enden Sie mit $ 83 $ vor $ 17 $ was falsch ist. Sie müssen den Haufen teilen, weil Sie die bisherige Sortierung des Algorithmus "erinnern müssen, was eher" wichtiger ist. Umgekehrt wird der erste Schritt der LSD-Radix-Sortierung $ 83 $ vor $ 17 $ , dann 19 $ $ . Wenn Sie den ganzen Stapel nehmen und von der ersten Ziffer sortieren, erhalten Sie $ 17 $ , $ 19 $ , < Span-Klasse="Math-Container"> $ 83 $ das ist korrekt. Sie müssen den Stapel nicht teilen, da der aktuelle Schritt des Algorithmus mehr "wichtig" der vorherigen ist, und es darf die vorherige Bestellung in irgendeiner Weise "durchführen" (z. B. durch Platzieren von $ 83 $ nach $ 17 $ und $ 19 $ ). Dies würde funktionieren, solange der für jede Ziffer verwendete Sortieralgorithmus stabil ist.