Radixsort
-
In Wikipedia steht, dass Radixsort lineares Laufzeitverhalten hat. Wäre es dann nicht für große Datenmengen gradezu ideal? Grade wenn es z.B. um das Sortieren von Integern geht, die ja bedingt durch den Wertebereich eine maximale Stellenanzahl haben, würde sich das doch anbieten. Bei komplexen Objekten kann man sicher im gegebenen Fall zumeist auch Integer-Hashs o.ä. bilden, die man sortieren könnte.
Trotzdem habe ich von Radixsort als schnellen Sortieralgorithmus eigentlich noch nie was gehört, die Wikipedia-Seite war ein Zufallstreffer.
Was ist der Grund, dass er in der Praxis eigentlich nicht eingesetzt wird?
-
Radisxsort: O(n * stellenzahl)
Anderssort: O(n* log2(n))
??stellenzahl>=log2(n)
!!Kannst auch heapsort als linear ansehen, wenn Du zufällig weißt, daß Dein Rechner eh nicht mehr als 1000000000 ints in ein Feld packen kann. Dann beschränkst Du es einfach auf O(n*30).
-
Ah ok, ich sehe den Denkfehler
(Wobei dein Beispiel nun grade schlacht war, denn die Stellenanzahl von 1000000000 ist mit 10 deutlich unter 30. Bei Logarithmen mit höheren Basen, z.B. Basis 10, stimmts aber)
Edit: du meinstest wahrscheinlich die Stellenanzahl im Binärsystem, nehme ich an? Gut, dann stimmts auch
-
ipsec schrieb:
Was ist der Grund, dass er in der Praxis eigentlich nicht eingesetzt wird?
Wahrscheinlich weil die Handhabung der Vergleichssortierer mit benutzerdefinierten Vergleichsfunktionen viel geschickter ist. Zudem dürfte radixsort erst bei sehr großen n schneller als qsort und Konsorten sein. Und vielleicht ist dieses n so groß, dass es für praktische Probleme nicht mehr relevant ist.
ipsec schrieb:
Bei komplexen Objekten kann man sicher im gegebenen Fall zumeist auch Integer-Hashs o.ä. bilden, die man sortieren könnte.
Ich glaube nicht, dass das so einfach ist. Du brauchst ja a) einen möglichst eindeutigen Hash und b) einen Hash der auch die Information der "Größe" eines Objektes beinhaltet.
-
Bei größeren Basen hast Du recht, sagen wir mal Basis 256. Dann brauchts für unseren int nur 4 Durchläufe! Leider ist es ein bißchen doof zu Implementieren. Aber wenn man es richtig anstellt, macht man std::sort damit platt.
Es ist generell eine gute Idee, Radix-Sort als Trumpfkarte in der Hinterhand zu haben. Aber man spielt sie sehr selten aus, weil die 30% Gewinn erkauft werden durch ein Festnageln an bestimmte Datenlagen. Später beim Kunden ist dann doch alles ganz anders. Und integers sind eh so schnell, wozu drüber nachdenken?Das mit dem hashen vergessen wir mal, denn die gehashten Daten willst Du dann sicherlich nicht in ein sortiertres Array stecken, sondern in eine Hashtable. Außer, es geht nur um sort-unique oder so.
-
volkard schrieb:
Radisxsort: O(n * stellenzahl)
Anderssort: O(n* log2(n))
??stellenzahl>=log2(n)
!!Kannst auch heapsort als linear ansehen, wenn Du zufällig weißt, daß Dein Rechner eh nicht mehr als 1000000000 ints in ein Feld packen kann. Dann beschränkst Du es einfach auf O(n*30).
Falsch. Die Basis des Logarithmus ist egal, da die Landau-Notation ja nur die Komplexität und nicht die eigentliche Anzahl an Vergleichen beschreibt. Es ist daher schwer, die ungefähre Anzahl an Operationen zu vergleichen.
Außerdem vermute ich mal, obwohl ich ihn nicht kenne, dass die Stellenzahl bei Radixsort binär ist.
-
wxSkip schrieb:
Außerdem vermute ich mal, obwohl ich ihn nicht kenne, dass die Stellenzahl bei Radixsort binär ist.
Die "grösse" einer "Stelle" bei Radixsort kannst du dir aussuchen. Damit indirekt auch die Stellenzahl.
D.h. du kannst auf N*log2(N) kommen oder auf N*log100(N) - ganz wie du willst.
-
Stimmt, Brett vorm Kopf.
Kann man also sagen, dass Radixsort auch n log n ist?
-
wxSkip schrieb:
Stimmt, Brett vorm Kopf.
Kann man also sagen, dass Radixsort auch n log n ist?Klar. Aber man benutzt es typischerweise nicht für BigInts, sondern nur für ints und schwupps, kann man ein konstantes m annehmen.
-
Dann hab' ichs also doch falsch verstanden! Aus den Forumsbeiträgen davor habe ich geschlossen, dass m die Arraygröße ist, doch ein RTM wirkt halt manchmal doch Wunder!
