Quote:
Originally Posted by MrSm!th
Die innere Schleife beim String-Vergleich (bzw. der Berechnung des Schlüssels) hat nichts mit Radix-Sort zu tun (hast du ja auch in einem Satz gesagt) und hat deshalb sowieso nichts in der Bewertung des Algorithmus zu suchen. Normalerweise nimmt man da der Einfachheit halber ohnehin Zahlen und keine Strings, damit der Vergleich nicht nur theoretisch, sondern auch praktisch als atomarer Schritt gewertet werden kann. Daran ist nichts schwammig.
Radix-Sort kann allerdings nicht in-place und stabil zur gleichen Zeit sein und ist daher in den meisten Fällen ungeeignet. Soweit ich weiß, lässt sich zeigen, dass es keinen in-place Algorithmus geben kann, der eine bessere Laufzeit als O(n*log2(n)) hat.
Edit: Ah ok, die Schranke bezieht sich auf vergleichsbasierte Verfahren.
|
Jap die Schranke gilt fuer vergleichsbasiert Verfahren.
Warum sollte Radixsort rausfliegen nur weil es nicht in-place sortiert werden kann?
Heutzutage sollte man doch genug Speicher besitzen, um auf O(n) Speicher verzichten zu koennen oder? Vorallem wenn man derartig grosse Daten sortieren will, dass man nur O(1) brauchen darf (was heutzutage wohl rund 8-16GB sind), dann frage ich mich ob man diese Daten ueberhaupt noch mit einem einzigen Rechner sortieren lassen will. Da das wohl sonst ewig dauert.
Selbst wenn man den Speicher dann doch braucht (zum Beispiel auf einen Microcontroller), kann man sich immer noch die Frage stellen, ob es wirklich wichtig ist, dass Strings/Zahlen stabil sortiert werden muessen (mir fallen dafuer nur ganz wenige Anwendungsgebiete ein).
Radixsort ist nur dann ungeeignet, wenn es sich um eine "Echtzeit"-Sortierung handelt, sprich wenn jedes Datum sofort richtig einsortiert werden soll, da man bei Radix-Sort immer alle, auch bereits sortierte Strings/Zahlen wieder sortieren muss.
Auch bei bereits vorsortierten Daten bietet sich eventuell Quick-Sort an.
Tatsaechlich achtet man bei den "Vergleichen" nicht auf die String-Laenge (normalerweise) bei Radix-Sort ist das aber anders, da eben dort Zahlen genau so sortiert werden wie Strings (naemlich Bit/Zeichenweise), deshalb verallgemeinert man das auf ein O(m*n), selbst fuer Strings, obwohl es dort offensichtlich eigentlich rausgeschmissen wird.
Genau aus diesem Grund habe ich es erwaehnt.
Ebenfalls ungeeignet ist Radix-Sort fuer die meisten "Zahl-Sortierungen", weil dort zwar immernoch theoretisch in O(n) sortiert wird (weil Zahlen eine feste Groesse besitzen), praktisch jedoch das Vergleichen von 2 Zahlen im Normalfall (bis zu einer gewissen Groesse der zu sortierenden Probleme) schneller ist als das Aufsplitten/Umsortieren/Speicher/Vergleichen/etc.
Fuer das Sortieren von einer grossen Menge von Strings (es macht ja eh erst Sinn ueber Laufzeit zu reden, wenn man grosse Stringlisten sortieren will, denn die kleineren Probleme laufen ja alle oft schnell genug ab) ist Radix-Sort jedoch der beste mir bekannte Algorithmus.
