Hallo zusammen
Ich hab mir in C++ einen Quicksort implementiert (ja ich weiss, STL. Wollte es einfach selbst schaffen...) Aus diversen Quellen weiss ich, dass sich der Best Case des Quicksort wie folgt berechnet:
O(n*log(n))
Wenn ich jetzt aber die Anzahl Schritte meines Quicksorts zähle, komme ich auf weniger
Entweder habe ich den ultimativen Sortieralgorithmus entdeckt, oder - wahrscheinlicher -mache ich einen Überlegungsfehler.
In meinem Beispiel handelt es sich um einen Array mit 14 Werten. Wende ich die Formel an, bekomme ich 14*log(14) = 16.04. Beobachte ich nun, was in meinem Algorithmus abläuft, sehe ich, dass dieser nur 10 Schritte benötigt:
4.29 8.84 2.98 7.32 8.79 2.19 3.95 4.55 9.38 9.81 2.99 3.14 0.55 2.19
2.19 0.55 2.98 3.14 2.99 2.19 3.95 4.55 9.38 9.81 8.79 7.32 8.84 4.29
2.19 0.55 2.98 3.14 2.99 2.19
2.19 0.55 2.19 3.14 2.99 2.98
2.19 0.55 2.19
0.55 2.19 2.19
2.19 2.19
2.19 2.19
3.14 2.99 2.98
2.98 2.99 3.14
4.55 9.38 9.81 8.79 7.32 8.84 4.29
4.55 4.29 7.32 8.79 9.81 8.84 9.38
4.55 4.29 7.32
4.29 4.55 7.32
4.55 7.32
4.55 7.32
9.81 8.84 9.38
8.84 9.81 9.38
9.81 9.38
9.38 9.81
Was mache / denke ich falsch? Vielen Dank für Eure Hilfe!
Marcel
