Frage zu Quicksort

[Guest]

Hi,

das allgemeine Prinzip von Quicksort habe ich verstanden, jedoch eine Frage:

Angenommen mein Zahlenfeld ist so:

5 2 9 3 1 6 8 10 7

Festgelegt habe ich das Pivot-Element auf die Mitte (zwar schlecht, aber ist nun mal so in meinem Beispiel. )
Dann wir 5 und 1 (Pivot) getauscht:

1 2 9 3 5 6 8 10 7

Wie wird jetzt das Pivot-Element bestimmt? Wenn ich 5 als Pivot nehme und von 2 bis 7 durchsortiere kommt ja:
1 2 5 3 9 6 8 10 7 raus und nun? Jetzt hab ich ja keine fertig sortierte Teilhälfte, aber das Pivotelement wurde ja trotzdem schon getauscht. ???:L

Gruß

 

[wolfgke]

Prinzipiell ist der Ansatz von Quicksort folgendermaßen:

0. Gegeben Liste l
1. Wenn l leer ist oder nur ein Element enthält: gib l zurück
2. Wähle Pivotelement p aus
3. Erstelle Listen l1, l2: l1 enthält alle Element aus l, die kleiner als das Pivot-Element sind, l2 die, die >= dem Pivot-Element sind (außer das Pivot-Element selbst)
4. rufe Quicksort für l1 und l2 auf. Heraus kommen sortierte Listen s1, s2
5. Gib Liste [s1, p, s2] zurück

Natürlich kann man das erheblich performanter machen

 

[Guest]

Na wie Quicksort funktioniert war mir ja klar, nur bin ich immernoch nicht schlau wie nun der nächste Schritt in meinem Beispiel ist.

Das mit 'Divide & Conquer' und das Prinzip hab ich verstanden. :roll:

 

[SlaterB]

> Dann wir 5 und 1 (Pivot) getauscht:

steht im krassen Widerspruch zu 3. aus wolfgkes Auflistung,
außerdem ist dort von zwei Teillisten die Rede, wo ist das bei dir?

du kannst doch nicht vom Algorithmus abweichen und trotzdem sagen, dass du alles verstanden hast

 

[Guest]

Wie würde denn eurer Meinung nach dann die Teilliste aussehen bei einem Pivotelement von 1 in der Mitte?
Das was ich gemacht hab war ja nur der erste Schritt ZUR Teilliste. Natürlich hatte ich noch keine 2 Teillisten nach dem 1. Schritt.

 

[SlaterB]

erstelle zwei neue Listen, durchlaufe alle Elemente und füge sie in eine der beiden Listen ein

 

[Guest]

Kannst du das nicht einfach an meinem Beispiel mit den Zahlen verdeutlichen?

Das Prinzip Pivotelement wählen -> Liste in 2 Teile einteilen und auf die beiden wieder den Algorithmus anwenden, bis man 2 ein-elementarige Teillisten hat, ist mir wie gesagt auch klar.

5 2 9 3 1 6 8 10 7

Wenn 1 nun mein Pivot ist, kann ich ja nicht einfach hingehen und sagen: "So, die 5, 2, 9 und die 3 kommen auf die rechte Seite und weiter gehts."
Normalerweise schaut man doch, ob links was größeres vom Pivot steht (ja, die 5 direkt) und rechts was kleineres (nein, also wird das Pivot mit der 5 getauscht). Das war aber nur der Tausch der 5 mit dem Pivot, die 2, 9 und 3 sind ja noch auf ihren alten Plätzen.

Hoffe, ich hab mein Problem nun verständlich erklärt.
Das Grundprinzip hab ich verstanden, nur die einzelnen Schritte detailliert...

 

[moormaster]

Normalerweise schaut man doch, ob links was größeres vom Pivot steht (ja, die 5 direkt) und rechts was kleineres (nein, also wird das Pivot mit der 5 getauscht).

Du kannst nicht einfach eine größere Zahl, die du findest, mit dem Pivot tauschen, weil du dann auch Zahlen auf die rechte Seite befördern könntest, die kleiner sind, als das Pivot... so kommt man nicht zum Ziel.

Wenn 1 nun mein Pivot ist, kann ich ja nicht einfach hingehen und sagen: "So, die 5, 2, 9 und die 3 kommen auf die rechte Seite und weiter gehts."

Warum nicht?
QuickSort(5 2 9 3 1 6 8 10 7 )
Pivot = 6 -> swap 9 1, swap 9 6: 5 2 1 3 6 9 8 10 7 (9 ist > 6 => auf rechte Seite befördern, indem sie zuerst ans Ende ihrer Teilliste getauscht und dann erst mit dem Pivot getauscht wird)
rekursive Aufrufe auf die Teillisten: QuickSort(5 2 1 3), 6, QuickSort(9 8 10 7)

usw.

 

[Guest]

Normalerweise schaut man doch, ob links was größeres vom Pivot steht (ja, die 5 direkt) und rechts was kleineres (nein, also wird das Pivot mit der 5 getauscht).

Du kannst nicht einfach eine größere Zahl, die du findest, mit dem Pivot tauschen, weil du dann auch Zahlen auf die rechte Seite befördern könntest, die kleiner sind, als das Pivot... so kommt man nicht zum Ziel.

Ich tausche die Zahl auf der linken Seite doch nur, wenn sie auch größer als das Pivot-Element ist. Zeig mir bitte ein Beispiel, wo das "bei meiner Version" der Fall sein könnte, vielleicht bringt mich das weiter.

Wenn 1 nun mein Pivot ist, kann ich ja nicht einfach hingehen und sagen: "So, die 5, 2, 9 und die 3 kommen auf die rechte Seite und weiter gehts."

Warum nicht?
QuickSort(5 2 9 3 1 6 8 10 7 )
Pivot = 6 -> swap 9 1, swap 9 6: 5 2 1 3 6 9 8 10 7 (9 ist > 6 => auf rechte Seite befördern, indem sie zuerst ans Ende ihrer Teilliste getauscht und dann erst mit dem Pivot getauscht wird)
rekursive Aufrufe auf die Teillisten: QuickSort(5 2 1 3), 6, QuickSort(9 8 10 7)

usw.

Ich hab es so gelernt, dass ich das Pivot-Element frei wähle, z.B. jetzt halt auf die 6 und dann von ganz links ein Zeiger durchläuft, der solange durchläuft, bis er etwas gefunden hat, was größer ist als das Pivot. Von ganz rechts läuft ein Zeiger, der solange sucht, bis er was gefunden hat, was kleiner ist als das Pivot. Wenn beide Zeiger was gefunden haben, werden diese beiden Werte vertauscht und die Zeiger laufen weiter. Sollte z.B. auf der linken Seite eine 8 gefunden sein, aber auf der rechten Seite gibt es kein kleineres Element mehr als das Pivot, dann wir die 8 mit dem Pivotelement vertauscht.

Stimmt das bis dahin?

 

[moormaster]

Ich hab es so gelernt, dass ich das Pivot-Element frei wähle, z.B. jetzt halt auf die 6 und dann von ganz links ein Zeiger durchläuft, der solange durchläuft, bis er etwas gefunden hat, was größer ist als das Pivot. Von ganz rechts läuft ein Zeiger, der solange sucht, bis er was gefunden hat, was kleiner ist als das Pivot. Wenn beide Zeiger was gefunden haben, werden diese beiden Werte vertauscht und die Zeiger laufen weiter. Sollte z.B. auf der linken Seite eine 8 gefunden sein, aber auf der rechten Seite gibt es kein kleineres Element mehr als das Pivot, dann wir die 8 mit dem Pivotelement vertauscht.

Stimmt das bis dahin?

Ja so sollte es auch funktionieren... ausser dass du dich entscheiden musst, was du mit Elementen machst, die den gleichen Wert, wie das Pivot haben... diese müssen entweder der linken oder der rechten Liste zugeordnet werden.

also so:
[ < Pivot]Pivot[ >= Pivot] oder [ <= Pivot]Pivot[ > Pivot] je nachdem, wie rum du das haben möchtest.

Es wäre auch [ < Pivot]Pivot Pivot ... Pivot[ > Pivot] möglich, ist aber evtl. etwas umständlicher.

 

[Guest]

Ok, dann ist das wenigstens schonmal korrekt. Und wie lautet genau das "Rüberschaffen" von Elementen? Ich dachte bisher, dass immer 2 Elemente getauscht werden (wenn links ein Element größer als das Pivot und wenn rechts ein Element kleiner als das Pivot ist). Wenn links kein größeres mehr ist, bzw. rechts kein kleineres mehr wird eben das Pivot-Element mit dem links größeren, bzw. rechts kleineren vertauscht. (Optimal wäre es ja, wenn es genau aufginge und das Pivot gar nicht getauscht werden muss, weil das Pivot dann ja schon an der richtigen Stelle ist und ich meine 2 Teillisten habe, jeweils links bzw. rechts vom Pivotelement.)

 

[moormaster]

Ok, dann ist das wenigstens schonmal korrekt. Und wie lautet genau das "Rüberschaffen" von Elementen? Ich dachte bisher, dass immer 2 Elemente getauscht werden (wenn links ein Element größer als das Pivot und wenn rechts ein Element kleiner als das Pivot ist).

Das hast du doch grad selbst beschrieben, wie das Rüberschaffen funktioniert?

 

[Guest]

Wenn ich das nach "meiner Version" mache, wird aber z.B. in der Liste:

5 2 9 3 1 6 8 10 7

die 5 mit der 1 (Pivot) getauscht, weil die 5 zwar größer als die 1 ist, aber auf der rechten Seiten sich nichts kleineres als die 1 finden lässt und der Zeiger somit bis auf das Pivotelement durchläuft.

Wenn das so richtig ist sieht es ja so aus:

1 2 9 3 5 6 8 10 7

Wie wird jetzt automatisch das Pivotelement gewählt, bzw. was wäre hier der nächste Schritt?

 

[moormaster]

Wenn ich das nach "meiner Version" mache, wird aber z.B. in der Liste:

5 2 9 3 1 6 8 10 7

die 5 mit der 1 (Pivot) getauscht, weil die 5 zwar größer als die 1 ist, aber auf der rechten Seiten sich nichts kleineres als die 1 finden lässt und der Zeiger somit bis auf das Pivotelement durchläuft.

Wenn das so richtig ist sieht es ja so aus:

1 2 9 3 5 6 8 10 7

Wie wird jetzt automatisch das Pivotelement gewählt, bzw. was wäre hier der nächste Schritt?

Ich dachte, du hast verstanden, wie Quicksort funktioniert? Was du jetzt gemacht hast, ist das wählen eines Pivots und das aufteilen in 2 Teilfolgen, die jeweils kleiner bzw. größer oder gleich dem Pivotelement sind.

Jetzt werden die linke Teilfolge (welche leer ist) und die rechte Teilfolge in einem rekursiven Aufruf wieder an deine QuickSortmethode übergeben. Die Ergebnisse der Aufrufe musst du nur wieder zu der gesamten Folge zusammensetzen

left = QuickSort()
right = QuickSort(2 9 3 5 6 8 10 7)

Ergebnis: left Pivot right

 

[Guest]

Ja... ok, Quicksort wird dann auf den Rest angewandt (der rechte Teil).

2 9 3 5 6 8 10 7

Als Pivotelement nehm ich dann z.B. die 6. Auf der linken Seite ist 9 die erste Zahl, die größer ist und auf der linken Seite gibt es nichts, also wird wieder das Pivotelement getauscht. Wenn ich das nun tausche:

2 6 3 5 6 8 10 7

sollte das getauschte Pivotelement (die 6) jetzt nicht eigentlich an richtiger Stelle stehen? Ist sie aber ja nicht, da die 3 z.B. noch danach kommt. Ist das vllt das, was du vorhin meintest, dass ich nicht einfach das Pivot tauschen darf? Wenn ja, wie geht es dann?

Tut mir echt leid, dass ich so sehr auf dem Schlauch stehe.

 

[moormaster]

Ja das wäre genau so eine Situation... du musst die 9 erst ans Ende ihrer Teilfolge tauschen (so dass sie neben dem Pivotelement steht)... erst danach darfst du sie mit dem Pivotelement vertauschen:

2 9 3 5 6 8 10 7 -> swap 9 5; swap 9 6 -> 2 6 3 6 9 8 10 7

 

[Guest]

Ok. Dann tuts mir leid, was ich bisher geschrieben hab, wir hatten das nie so, dass man die Zahl ans Ende der Teilliste tauscht und dann erst mit dem Pivotelement.

Nun macht Sinn.. danke! :applaus:

 

[moormaster]

Ich kann nicht sagen, ob >man< das so macht... ich würde es jedenfalls so machen

 

[Guest]

Ich kann ja einfach mal "meine" Version von Quicksort posten:

public void sort () {
quickSort(0,elemente.length-1); 
}

private void quickSort(int links, int rechts) {
Inhalt x = elemente[(links+rechts)/2];
int i = links, j = rechts;
do {
  while (elemente[i].compareTo(x) < 0)
    i++;
  while (elemente[j].compareTo(x) > 0)
    j--;
  if (i < j) {
    Inhalt help = elemente[i];
    elemente[i] = elemente[j];
    elemente[j] = help;
  }
  if (i <= j) {
    i++; j--;
  }
} while (i <= j);
if (links < j)
  quickSort(links,j);
if (i < rechts)
  quickSort(i,rechts);
}

Kann da jedenfalls kein "Vertausche-Element-mit-Element-am-Ende-der-Teilliste" erkennen.