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:

markieren

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

markieren

Code:

Pivot := A[Hi]

und beim average case

markieren

Code:

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

Und die Zahlen sind wie gesagt am Anfang falschherum sortiert.

Wo liegt denn jetzt der Fehler?

Deine while-Schleife mit Einrückung:

markieren

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.

ES FUNKTIONIERT!!! Dankedankedanke

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

Sherlock

Womit wir wieder beim Thema Formatierung wären

Aber bitte keinen Glaubenskrieg.