QuickSort - Pivot in der Mitte

[cod3r]

Hallo zusammen,

ich habe als erstes einen QuickSort-Algorithmus programmiert bei dem das Pivotelement in jedem Aufruf ganz rechts steht. Funktioniert auch soweit. Jetzt wurde mir die Aufgabe gestellt, einen QuickSort-Algorithmus zu erstellen bei dem das Pivotelement bei jedem Aufruf in der Mitte steht. Hier habe ich ein Problem 🙂

Mein zu sortierendes Array lautet: A = [3,4,7,10,6,8,1,9,2,5]

juti, das Pivotelement lautet: "6"

Code-Snippet:

[JAVA=42]
int A[] = {3,4,7,10,6,8,1,9,2,5};

public static void quicksort (int A[], int li, int re) {


if (li > re) return; /* Falls die ganz linke Position im Array
* kein Folgeelement mehr hat brich ab!
*/
else
{

int k; // Zaehlvariable
int l = 0; // Variable fuer den linken Zeiger
int r = re; // Variable fuer den rechten Zeiger
int tmp; // Variable fuer die Zwischenspeicherung beim Tausch
int pivot = A[(li+re)/2]; // Pivotelement

//-----------------------------------------------------------------------------------//

for (k=0; k<re; k++)
{
while (A[l] <= pivot) {l++;}
while (A[r] >= pivot) {r--;}

if (l>r) break;
else {tmp = A[l]; A[l] = A[r]; A[r] = tmp;}
}
[/code]

[JAVA=42]
quicksort(A,li,pivot-1);
quicksort(A,pivot+1,re);
[/code]

O.K. - wenn ich jetzt den Zeigerdurchlauf nachvollziehe, dann ergibt sich folgendes Bild:
"l läuft bis 7 - r bleibt bei 5" - Tausch
"l läuft bis 10 - r läuft bis 2" - Tausch
"l läuft bis 6 (Pivot) - r läuft bis 1" - ???

Hier ist mein erstes Problem, mein linker Zeiger kommt am Pivotelement an, rechter Zeiger hat aber noch Elemente vor sich.
Wird hier das Pivotelement dann mit dem Element des rechten Zeigers vertauscht?

 

[SlaterB]

kannst du bitte das funktionierende Quicksort-Programm posten?!
wenn du dort auch nur in einem Array vertauschst, frage ich mich wirklich wie das aufgebaut ist,

ansonsten zwei Wiki-Zitate

Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
[..]
Die Längen der Teillisten ergeben sich aus der Wahl des Pivotelements. Idealerweise wählt man das Pivot so, dass sich zwei etwa gleich lange Listen ergeben, dann arbeitet Quicksort am effizientesten. Es sollte also etwa gleich viele Elemente kleiner als das Pivot und größer als das Pivot geben.

Quicksort ? Wikipedia

schon aus diesen einleitenden Sätzen klar, dass du irgendwas anderes programmierst?
du brauchst Teillisten oder musst meinetwegen im Array die Grenze verschieben können,
nur links mit rechts vertauschen ist zu wenig, wie du selber merkst

 

[Dekker]

Naja ich steige nicht durch die untere Zeile die er geschrieben hat also das zweite Codebeispiel. Ich glaube du hast den Algorithmus bissle falsch verstanden. Seh dir am besten wirklich mal den Wikipedia Pseudocode an. Deinen Pivotalgorithmus benutzt du halt anstelle

 pivot := daten[rechts]

sowas wie

 pivot := computePivot()

und in computePivot() berechnest du dann den Index deines Pivotelements.

 

[NamenVergeben]

Ich zitiere mal Wikipedia:

// Starte mit j links vom Pivotelement

Also ich denke, man nimmt sich das Pivotelement beliebig und vertauscht es mit dem Ende und benutzt dann den bekannten Algorithmus für die Liste davor. Am Schluss wird das Element dann wieder in die Liste "getauscht" und man weiß auch definitiv, wo es sich befindet.

Ansonsten bekommt man eine falsche Sortierung, bleibt in einer Endlosschleife stecken oder braucht zusätzliche Abfragen, so wie ich das sehe...
Wenn es anders eleganter geht, bitte ich um genaue Informationen, wo dies steht. Es interessiert mich auch sehr 🙂

 

[cod3r]

Hi 🙂

Danke für die zahlreichen Antworten. Ja, leider ist es wirklich so, dass das Pivotelement immer in der Mitte sein soll. Das hat auch soweit geklappt nach dem ich mir durch "aufmalen" bewusst gemacht habe wie das abläuft. Den entsprechend funktionierenden Quellcode habe ich angehängt.

Grüße!

 

[NameVergeben]

Danke für deine Rückmeldung.
Scheint zu funktionieren. Bloß, dass du jetzt das Pivotelement doppelt sortierst.
Ist die Frage, ob es dann nicht einfacher ist, einfach das Pivotelement an den Schluss zu tauschen und dann zu sortieren.

Vllt. hätte man sich auch einfach die Position des Pivotelements merken können, um dann den bekannten Algorithmus benutzen zu können.