Quicksort worst/best/average case

[Katehe]

Hallo liebe delphi- community,
ich hätte da eine Frage zum Thema Quicksort. Ich habe mein Programm so geschrieben, dass es mir dir Anzahl an Vergleichen, die es gemacht hat, am Ende wieder rausgibt. Dann habe ich einmal den worstcase durchlaufen(Zahlen Sortiert von 100 bis 0, pivot immer ganz rechts bei der kleinsten zahl) und es kamen 400 vergleiche raus. Das selbe habe ich mit dem best case gemacht und es waren 189. Soweit so gut. Wenn ich jetzt aber den average case versuche, mit pivot=random, kommen teilweise mehr Vergleiche als bei dem worst case oder weniger als bei dem best case raus.

Hier nochmal die Quellcodes dazu:

Code:

begin
   Lo := iLo;
   Hi := iHi;
   Pivot := A[(Lo+Hi) div 2];
   repeat
     while A[Lo] < Pivot do Inc(Lo) ;  n:=n+1;
     while A[Hi] > Pivot do Dec(Hi) ;  n:=n+1;
     if Lo <= Hi then
     begin
       T := A[Lo];
       A[Lo] := A[Hi];
       A[Hi] := T;
       Inc(Lo) ;
       Dec(Hi) ;
       n:=n+1;
     end;
   until Lo > Hi;
   if Hi > iLo then QuickSort(A, iLo, Hi) ;
   if Lo < iHi then QuickSort(A, Lo, iHi) ;

Aalso bis auf das pivot bleibt ja alles gleich, das war eben mein best case, bei dem worst case ist das pivot wie schon gesagt

Code:

Pivot := A[Hi]

und beim average case

Code:

Pivot := A[random(Hi-Lo)+Lo]

Und die Zahlen sind wie gesagt am Anfang falschherum sortiert.

Wo liegt denn jetzt der Fehler?

[jfheins]

Deine while-Schleife mit Einrückung:

Delphi-Quellcode:

while A[Lo] < Pivot do
    Inc(Lo);
n:=n+1;

Falls du mehr als ein Statement in den Schleifenkörper setzen möchtest, muss du begin/end verwenden.

[Katehe]

ES FUNKTIONIERT!!! Dankedankedanke :D :wall: :wall: :wall: :party:

[Sherlock]

Das hätte Dir mit automatischer (vernünftiger) Codeformatierung auch selber auffallen können.

Sherlock

[DeddyH]

Womit wir wieder beim Thema Formatierung wären :mrgreen:

[Dejan Vu]

Aber bitte keinen Glaubenskrieg.