Ich versuche, die Gefahr bei der Verwendung eines instabilen Sortieralgorithmus (wie Quick-Sortierung) in Radix-Sortierung zu verstehen. Auch muss stabiler Algorithmus in beiden Fällen (d. H. MSD Radix sort und LSD Radix sort)?Was ist die Notwendigkeit, nur einen stabilen Sortieralgorithmus für die Radix-Sortierung zu verwenden?
Vielen Dank im Voraus.
MSD-Radix-Sortierung ist normalerweise nicht praktikabel, da die virtuellen Bins nach jedem Durchlauf nicht verkettet werden können. Wenn Sie nach 8 Bit sortieren, haben Sie nach dem ersten Durchlauf 256 separate Bins, nach zwei Durchläufen 65536 Bins, nach drei Durchläufen 16777216 Bins, ....
LSD Radix Sort muss stabil sein, da die virtuellen Bins der Reihe nach verkettet werden und die folgenden, die wichtigeren "Ziffern" durchlaufen, müssen die Reihenfolge der vorherigen Pässe beibehalten. Beachten Sie, dass die LSD-Radix-Sortierung die alten Kartensortierer aus dem frühen 20. Jahrhundert verwendet.
http://en.wikipedia.org/wiki/IBM_card_sorter#Earlier_sorters
Was meinen Sie mit * wird den Job *? Wenn Sie meinen, dass die Ausgabe sortiert wird, dann beachten Sie bitte, dass Radix sort on MSD (stabil/instabil) auch die Aufgabe erfüllt. Wenn Sie meinen, dass der Algorithmus stabil sein wird, warum sagen Sie dann: * any (stabil/instabil) * wird die Aufgabe übernehmen, weil ein instabiler Algorithmus offensichtlich nicht stabil ist? Was ist der * Job * von dem du sprichst? – trincot
Nachdem ich Ihren Kommentar gelesen hatte, erkannte ich die Zweideutigkeit in meiner Frage. Außerdem erkannte ich, dass mein Verständnis von Radix-Art nicht ganz richtig war. Ich habe die Beschreibung bearbeitet. –
OK, was meinst du mit * ist stabiler Algorithmus muss *: Ich verstehe das Wort * muss * in diesem Zusammenhang nicht. – trincot