Stehe auf dem Schlauch bei Quicksort

[carom]

Hallo!

Habe gerade ein Brett vor dem Kopf und komme nicht weiter, obwohl es sicherlich so einfach ist.

• Generell gilt bei Quicksort ja, dass man für das beste Reultat das Pivot-Element möglichst so wählen sollte, dass es ca. gleich viele kleinere und größere Elemente drum herum gibt.
• Davon abgesehen ist es aber prinzipiell egal, was als Pivot-Element gewählt wird. Viele Algorithmen nehmen ja auch einfach Random() her, um den Pivot zu bestimmen.
• Nach einem Durchlauf sollte das Pivot-Element ja bereits schon an seiner endgültigen Stelle stehen und es geht mit einem anderen Pivot im nächsten Durchlauf weiter.

Schön und gut, folgende Zahlenreihe:

5 1 2 3 4

4 sei der Pivot für Durchlauf 1.
Mit i = 0 fange ich von links an, nach einem Element >= 4 zu suchen und werde mit der 5 auch sofort fündig. Mit j = 4 fange ich von rechts an nach einem Element <= dem Pivot zu suchen und werde auch direkt fündig, mit dem Pivot selbst. Dann tauschen und es sieht so aus:

4 1 2 3 5

Schon mal besser als zuvor, aber ohne überhaupt weiterzumachen nun meine Denkblockade: es läuft ja immer noch der erste Durchgang mit Pivot 4. Allerdings ist i mittlerweile auf 1 erhöht und wandert nach rechts, d.h. die 4 ganzs links wird gar nie mehr angerührt in Durchgang 1. Aber dann steht sie nach diesem Durchgang ja definitiv auch nicht an ihrer endgültigen Stelle (was aber so sein müsste)?


Ich weiß, dass das eigentlich keinen Thread wert ist weil es irgend ein kleines Problem ist, aber sehe gerade den Wald vor lauter Bäumen nicht.

Danke.

 

[holy]

Dein Problem ist, dass du den Algorithmus falsch anwendest.
Der Sinn von Quicksort ist es ja, die eigentliche Liste so lange in Teillisten zu teilen, mit der Bedingung, dass alle Elemente links kleiner als das Pivot sind und alle rechts größer sind, bis die Urliste sortiert ist. Das Pivot-Element stellt dabei den "Trenner" dar.

Wenn du mit 4 anfängst, dann startet dein j nicht bei 4, sondern eine Stelle weiter links. Generell, startest du i und j nicht mit dem Pivot. Andernfalls kannst du die Bedingung auch gar nicht erfüllen.

Bsp.

p = 4, i läuft von links nach rechts, j von rechts nach links.

5 1 2 3 4

i = 5, j = 3, p = 4
==> i >= 4, j <= 4 ==> tauschen


3 1 2 5 4

i = 1, j = 2, p = 4
==> j <= 4, j wartet, i läuft weiter.

i = 5, j = 2, p = 4
==> i an j vorbeigelaufen => Abbruch. Und nun der Clue tausche p mit i.

3 1 2 4 5

Und nun ist die Bedingung erfüllt. Links neben den Pivot ist alles kleiner, rechts alles größer.

Edit.
Denke, du weißt jetzt wie es weiter geht. Nun hast du 2 Listen, 3 1 2 und 5, die du nun nach dem gleichen Prinzip weiter sortieren musst.

 

[carom]

Danke mal.

Ok, anders gefragt. Wieder 5,1,2,3,4 - Pivot sei nun 2. Könntest du hier bitte nochmal kurz die erste Vertauschung schildern?

 

[yoT!mO]

Schau dir mal folgendes Video an

http://www.youtube.com/watch?v=ywWBy6J5gz8

Ich glaub, viel anschaulicher kann man es net zeigen

Gruß Timo

 

[Yuuri]

Epic! Danke dafür.

 

[dcobra]

e: hier stand müll

 

[Furtano]

Schau dir mal folgendes Video an

http://www.youtube.com/watch?v=ywWBy6J5gz8

Ich glaub, viel anschaulicher kann man es net zeigen

Gruß Timo

omg rofl xD

 

[Uhu911]

Hallo, ich muss mich mal an diese Frage anschließen, da ich über eine Google-Suche auf den Tread gekommen bin.
Vom Ablauf her verstehe ich den Quicksort, allerdings fällt es mir schwer, ihn in Code umzumünzen. Irgendwie will er nicht ganz durchsortieren.
Der folgende Code ist in Pascal, aber man sollte ihn durchaus verstehen. Es wäre super, wenn mir jemand helfen könnte.

Procedure quickSort2 (var iArray : array of integer; links : integer; rechts : integer);
      var pivotElement : integer;

     Function getPivotElement (var iArray : array of integer;links: integer; rechts: integer):integer;
              var li, re, pivot : integer;
     begin
       li := links;
       re := rechts;
       pivot := iArray[rechts]; // Pivot auswählen
       re := rechts-1;          // rechten Startwert vom Pivot entfernen

       while (li<re) do begin
           // so lange man nicht aneinander vorbei gelaufen ist
           while (iArray[li] < pivot) AND (li < rechts) do li := li+1;
           while (iArray[re] > pivot) AND (re > links) do re := re-1;
           // Jetzt haben wir je einen Index li und einen Wert re für die wir wissen, dass der Wert li größer oder re
           // kleiner als der Pivot sind (Ausnahme: Man ist bis ganz zum Ende durchgelaufen, weil man gar nix gefunden hat
           // deshalb in der nächstne Zeile: if
           if (li < re) then swap(iArray,li,re);
     end;
       // Wenn alle Umsortierungen getan sind, dann muss noch der Pivot an die korrekte Stelle:
          swap(iArray,rechts,re);
          getPivotElement := li;
       end;


 begin
   if (links < rechts) then begin
      pivotElement := getPivotElement(iArray, links, rechts);
      quickSort2(iArray,links,pivotElement-1);
      quicksort2(iArray,pivotElement+1,rechts);
  end;

  end;

Zum Beispiel erzeugt die Eingabe 895643189 die Ausgabe 145368899

Irgendwie muss hier also noch besser durchsortiert werden.