Problem mit QuickSort

[Alexander Bajic]

Hallo,

ich habe ein Problem mit meinem implementierten Quicksort. Es fing damit an,
dass mein Quicksort immer einen sehr hohen Aufwand hatte, weil ich mein
Pivot-Element vom rechten Rand gewählt habe..... das hat soweit auch
funktioniert. Mir viel aber später auf, dass ich dadurch einen Nachteil
habe, gerade, wenn mein Array schon vorsortiert ist, ackert er wie ein
verrückter, weil das Element ganz rechts nunmal das größte ist. Das heißt,
dass ich durch meine Vorsortierung nix gewonnen habe.

Also dachte ich mir, dass ich schlau wäre, wenn ich das Pivot-Element auf
den Index [(start+end)/2] setze. Jetzt muss ich aber feststellen, dass mein
Quicksort nur noch mist baut. Ich teste das ganze an einem Array, der
Abwärts-sortiert ist. das heißt ich habe 100 Elemente, startend bei 100 und
endend bei 1. Er wählte also immer die kleinste Zahl als Pivot-Element. Habe
es jetzt mehrfach mit anderen Indizes getestet....... er macht immer mist,
mal siehts besser, mal siehts schlechter aus.... richtig funktionieren tuts
echt nur bei pivot=a[end].

Habe schon gesucht wie ein verrückter, aber nix gefunden. Laut recherche im
internet ist mein Algorithmus aber richtig (vergleich bei Wikipedia zu
Beispiel).

Evtl. kann ja jemand anders mal einen Blick drauf werfen, denn ich sehe dort
nix. habe die relevanten Stellen einfach mal eingefügt.

Danke

Alex

public static void quickSort(Comparable[] a, int start, int end)
{
int part;
if(start<end)
{
part=partition(a, start, end);
quickSort(a, start, part-1);
quickSort(a, part+1, end);
}
}

public static int partition(Comparable[]a, int start, int end)
{
Comparable element;
int part=start;
Comparable pivot=a[(end+start)/2];

for(int i=start; i<end; i++)
{
element=(Comparable)a[i];
if(element.compareTo(pivot)<=0)
{
swap(a, i, part);
part++;
}
}
swap(a,part,end);
return part;
}

[Alexander Bajic]

Hmmm..

ist ja fast ein wenig peinlich..... habe meinen Fehler gefunden, leider erst
30 Sekunden anchdem ich gepostet habe.
Für andere die den beitrag schon gelesen haben und auch der Meinung sind,
dass alles korrekt sei, hier die Lösung:

Das mittlere Element kann nicht einfach so gewählt werden, weil der
Quicksort ja so aufgerufen wird, dass das allerletzte Element niemals von
der for-Schleife berührt wird, es ist also vor Manipulationen geschützt.
Wenn ich jetzt einfach das Element in der Mitte nehme, dann wars das mit der
exclusiven Position. Aus diesem grund habe ich einfach das hintere und das
mittlere Element miteinander vertauscht und anschließend einfach a[end] als
Pivot-Element genutzt.

Gruß

Alex
"Alexander Bajic" <alexand...@gmail.com> schrieb im Newsbeitrag
news:4flodfF...@news.dfncis.de...