Zitat von
alzaimar:
Ich glaub, Du verwechselst da was. Es gibt natürlich Sortierverfahren, die linear sortieren, aber dazu musst Du Einschränkungen in Kauf nehmen. Du must spezielle Kentnisse über den Schlüssel verwenden (Zahl zwischen 1 und X oder so).
Es ist schon bewiesen, das allgemeine Sortierverfahren im Optimum einen Aufwand von O(n log n) haben. Besser geht es einfach nicht. Jedenfalls nicht in diesem Universum.
Ja, wie gesagt mit starken Einschränkungen kann man linear Sortieren. Für Counting und Radixsort sollte dass sicherlich die Beschränkheit der Schlüssel sein (auch sollte X nicht zu groß sein, auch Speicher muss nicht verschwendet werden). Eine andere Möglichkeit besteht im Bucketsort, da muss ich "nur" Schlüssel gleichverteilt im Interval [quote=alzaimar]st auch der Linear.
Aber wie gesagt es sind starke Einschränkungen.
Zitat von
alzaimar:
Mergesort im Speicher ist auch bei einigen Millionen Elementen *viel viel* langsamer als Quicksort. Probierts doch einfach aus. Theorie hin oder her, Quicksort, (eventuell iterativ), ist einfach am Schnellsten, auch wenn im 'worst case' Mergesort theoretisch(!) schneller ist.
Ich dachte eigentlich in Erinnerung zu haben, dass man durch dass geschickte Teilen beim Mergesort und genügend Elementen schneller werden kann als mit dem Quicksort. Lag dann daran, dass die gesamte Sortierung immer im schnellen Hauptspeicher stattfinden kann und ich die Teilfelder sogar Parallel sortieren könnte. Da ich beim Quicksort immer alle Elemente mit dem Pivotelement vergleichen muss, geht dass dort nicht (schlechter / weniger effizient).
Aber kann mich da auch total vertun (was mir dann zwar peinlich wäre, aber egal, man lernt ja gerne dazu!).
Allerdings würde dass natürlich auch nur etwas mit Optimierung des Mergesorts, sehr großen Datenmengen und paralleler Verarbeitung bringen, sonst bleibt es Fakt, dass die Konstanten Faktoren des Mergesort größer sind als die des Quicksort.
Aber wo ich mir auch noch recht sicher bin, bei sehr kleinen Mengen ist Bubblesort wiederum schneller als Quicksort. Wenn ich mich da an wirklich optimale (nicht nur bis auf konstante Faktoren) Sortieralgorithmen erinnere, werden nur Felder bestimmter Größe mit Quicksort sortiert. Ist ein Teilfeld erstmal klein genug, wird ein anderer verwendet (denke es war dort sogar Bubblesort).
Egal, jedenfalls ist der Worst-Case gerade beim Quicksort einfach mal Theorie und die Rechnung des Average-Case anstrengend, wenn man nicht wirklich zig-Tausend oder millionen Einträge sortiert, denke ich wird man den Unterschied zwischen den beiden auch noch verkraften können (nicht immer!).
Gruß Der Unwissende