QuickSort will mir nicht in den Kopf (an einer Stelle)

[Samuel]

Wir hatten QuickSort in Info in der Schule und wir hatten QuckSort im Studium.

Knapp zusammen gefasst: Man nimmt sich mittleren Wert aus, sagen wir, einem int Array und fängt dann an
von links zu gucken, was größer als der Wert der Mitte und von rechts was kleiner ist, dann wird getauscht.
Das tut man solange, bis die linke Seite die rechte erreicht hat, aber meine Frage:
Was macht Quicksort, wenn der rechte Wert bereits links vom Mittelwert, aber noch nicht am linken Laufwert ist?

Ich hab hier mal ein Beispiel:
10,8,1,6,0,4,7,5,2, ich nehme hier mal zur Verdeutlichung die 4 als Mittelwert

1. Phase
10,8,1,6,0,4,7,5,2
die roten werden getauscht
2. Phase
2,8,1,6,0,4,7,5,10
jetzt wird die 8 bereits mit dem Mittelstring getauscht, aber man guckt
weiterhin ob links und rechts in relation zu 4 stehen, also dem alten Mittelstring
3.Phase
2,4,1,6,0,8,7,5,10 (4 war der Vergleichswert)

Aber was tut Quicksort hier? dreht es die beiden einfach um? Welchen Sinn hat das?
Die 4 stand so oder so rechts von beiden, der tausch an dieser Stelle bewirkt doch
eigentlich kein bisschen was, oder irre ich mich?

 

[Bleiglanz]

Ja, ein Implementierungsfehler

6 und 0 werden bei einem richtigen Quicksort NIE miteinander verglichen (zumindest in dieser Runde), ein Vertauschen wär sinnlos

BTW: rede nicht vom "Wert", sondern von der "Position"; dass das Pivotelement den Wert=4 hat ist völlig belanglos; interessant ist nur, dass man dass Array an der 6. Stelle zerlegt hat

[edit] das ist völliger Quatsch

 

[Samuel]

Der Code ist der:

static void qSort(int[] f, int lPos, int rPos){
		   int lTemp, rTemp, h;
		   if (lPos < rPos){
		     lTemp = lPos; rTemp = rPos; int x = f[(lTemp+rTemp)/2];
		     
		     do { // grösser x nach rechts, kleiner x nach links:
		      
		       while (f[lTemp] < x) {lTemp++;  // wandere von links kommend
		       
		       }
		       while (f[rTemp] > x) rTemp--;  // wandere von rechts kommend
		       // Austausch der Werte:
		       if (lTemp <= rTemp) {
		         h=f[lTemp]; f[lTemp]=f[rTemp]; f[rTemp]=h;
		         lTemp++; rTemp--;
		       }
		     } while (lTemp <= rTemp);
		     // jetzt noch linke und rechte Seite (rekursiv) sortieren:
		     
		     qSort(f, lPos, rTemp);  // rTemp ist jetzt kleiner lTemp (siehe while-Abbruch!)
		     qSort(f, lTemp, rPos);  // s.o.
		  }
		 }

Das Ding funktioniert jedoch recht gut

 

[Bleiglanz]

glaub ich jetzt nicht unbedingt

             while (f[lTemp] < x) {lTemp++;  // wandere von links kommend
             
             }  // die hier ist komisch??

[edit] auch quatsch

 

[Samuel]

Sorry, muss so aussehen, war nur n versuch von was anderen

static void qSort(int[] f, int lPos, int rPos){
         int lTemp, rTemp, h;
         if (lPos < rPos){
           lTemp = lPos; rTemp = rPos; int x = f[(lTemp+rTemp)/2];
           
           do { // grösser x nach rechts, kleiner x nach links:
           
             while (f[lTemp] < x) lTemp++;  // wandere von links kommend
             while (f[rTemp] > x) rTemp--;  // wandere von rechts kommend
             // Austausch der Werte:
             if (lTemp <= rTemp) {
               h=f[lTemp]; f[lTemp]=f[rTemp]; f[rTemp]=h;
               lTemp++; rTemp--;
             }
           } while (lTemp <= rTemp);
           // jetzt noch linke und rechte Seite (rekursiv) sortieren:
           
           qSort(f, lPos, rTemp);  // rTemp ist jetzt kleiner lTemp (siehe while-Abbruch!)
           qSort(f, lTemp, rPos);  // s.o.
        }
       }

 

[Bleiglanz]

immer noch nicht

while (f[lTemp] < x) lTemp++;

hamm ersetz das durch

lTemp = x

und du hast das gleiche

[edit] nochmal quatsch

 

[Samuel]

Wieso? mit der While sucht man doch Werte links und rechts von dem Pivot?

 

[Bleiglanz]

tipp

{



}

 

[Samuel]

Klammern, was soll ich mit Klammern?

Der QuickSort da oben funktioniert doch, wir haben den auch vom Prof bekommen.
Ich wundere mich nur, dass dieser doch auch wie oben beschrieben tauscht

 

[Bleiglanz]

Klammern, was soll ich mit klammern?

Der QuicSort da oben funktioniert doch, wir haben den auch vom Prof bekommen.
Ich wqundere mich nur, dass dieser doch auch wie oben beschrieben tauscht

ah, quatsch, hab mich verlesen

sollte schon passen!

 

[Samuel]

Kp, aber was ich meine ist, ich sehe doch richtig, dass dieser, wie oben beschrieben, auch 6 mit 0 tauschen würde, oder?

 

[Bleiglanz]

L10,8,1,6,0,4,7,5,R2

der pivot ist 4

von links-kommend landen wir bei 10 (weil nicht < 4)
von rechts-kommend landen wir bei 2 (weil nicht > 4)
vertausche

2,L8,1,6,0,R4,7,5,10

jetzt von links bei 8 weil nicht < 4
jetzt von rechts bei 4 weil nicht > 4
vertausche

2,4,1,L6,R0,8,7,5,10

von links bei 6 weil nicht < 4
von rechts bei 0 weil nicht > 4
vertausche

jetzt aber L=R, Ergebnis

2,4,1,0,6,8,7,5,10

und das aufteilen liefert

2,4,1,0 (die kleiner oder gleich pivot)

und

6,8,7,5,10 (die grösser als der pivot)

ist also alles völlig in butter, er muss (!) nochmal tauschen

 

[Samuel]

Also es ist ok, dass man 6 und 0 tauscht, obwohl bei bereits links vom Pivot sind?

 

[Bleiglanz]

ja, muss sogar

ich hab oben ziemlichen Unsinn geschrieben, es geht nicht um "links" oder "rechts", sondern um grösser oder kleiner

der Wert des Pivots ist entscheidend, nicht seine ursprüngliche Position

er ist ja in dem Beispiel schon auf Position 2 gerückt, aber das ist ganz egal

das wandern von links und rechts geht solange weiter bis sich die beiden Wanderer in der mitte treffen, und dieser Punkt ist dann der Zerlegungspunkt; und der Algo stellt einfach sicher, dass

alles links von diesem Treffpunkt <= dem Wert des Pivots

alles rechts von diesem Treffpunkt > dem Wert des Pivots

 

[Samuel]

Alles klar, hatte immer das Bild, das genau in der Mitte zerlegt wird, aber nun ist alles klar.
Danke