Dr. Solution

Das ist auch keine Formel, in die du für n irgendetwas einsetzen könntest.

Sie sagt nur aus, wie sich der Algorithmus in Abhängigkeit von der Anzahl der Elemente verhält

Also kann ich doch für n die Anzahl Elemente einsetzen, oder?

Die O-Notation sagt nichts über die Anzahl der "Schritte" (Vertauschungen oder Vergleiche) aus. Das ist auch keine Formel, in die du für n irgendetwas einsetzen könntest.

Aha! Was sagt die Formel denn genau aus?

Mir geht es darum, in meiner Applikation während dem Sortieren einen Progress-Balken anzuzeigen. Dafür wäre es hilfreich, die Anzahl Sortierschritte ungefähr voraussagen zu können.

Danke und Gruss

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