Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

[Der_Unwissende]

Na dann wünsch ich dir mal viel Glück.
Wenn du lineare Zeit hast, dann ist das trotzdem schneller als jeder bekannte Sortieralgorithmus! Konstante Faktoren können beliebig groß werden, dass macht keinen Unterschied aus, ergo ist langsam hier falsch. Sagen wir du hast 1.000.000.000 * n Schritte zum Sortieren und sagen wir mal ganz einfach, Bubblesort braucht genau n^{2} Schritte. Dann würde das lineare Sortieren mit n > SQRT{1.000.000.000} schneller sein als Bubblesort.

Wichtiger ist aber, dass du mit einer CPU die 1.000.000.000 mehr Operationen pro Zeit schafft, du einmal auch wirklich 1.000.000.000 mehr Elemente pro Zeit sortieren kannst, bei Bubblesort sind es aber nur SQRT{1.000.000.000} ^= 31.600 mehr Elemente.
Darum geht es eigentlich, schnell oder langsam hängt irgendwo auch von der CPU ab, aber die ist nicht immer gleich. Wenn ich in 3 Sek. sortieren kann, was heißt das? Du weißt ja nicht womit ich wie sortiert habe. Ändert sich die CPU, ändert sich aber nichts an der Asymptotischen Betrachtung. Die Anzahl der Rechenschritte bleibt gleich.

Gruß (und viel Glück beim Finden) Der Unwissende