von namroon » 28.07.11 12:35 mein Übungspartner und ich haben ein Problem mit der Miniklausur zu Quicksort:
Benutzen Sie Quicksort, um das folgende Array aufsteigend zu sortieren
5, 1, 3, 10, 5, 7, 6
Verwenden Sie jeweils das Element mit dem kleinsten Index als Pivotelement.
Achten Sie darauf, daß alle Schritte gut nachvollziehbar sind!
Algorithmus aus der Vorlesung:
- Code: Alles auswählen
procedure quicksort(L, R) :
if R ≤ L then return fi;
p := a[L]; l := L; r := R + 1;
do
do l := l + 1 while a[l] < p;
do r := r − 1 while p < a[r ];
vertausche a[l] und a[r ];
while l < r ;
a[L] := a[l]; a[l] := a[r ]; a[r ] := p;
quicksort(L, r − 1); quicksort(r + 1, R)
Wenn wir Schritt für Schritt den Algorithmus durchgehen überschreiben wir uns an einer Stelle eine Zahl und finden unseren Fehler einfach nicht. Ich hoffe Ihr könnt die Lösung nachvollziehen, falls nicht fragt bitte noch mal nach.
Lösungsansatz:
- Code: Alles auswählen
aktuelles Pivot [x]
aktuell sortiert (x)
tausche x mit y x*<->y* bzw x°<->y°
verschiebe Zahl x von a nach a' in lexikographischer Reihenfolge
1 2 3 4 5 6 7 8
-------------------------------------------------------------- quick(1,7);
[5] 1 3 10* 5* 7 6 p=5
l0 l1 l2 l3
r3 r2 r1 r0
[5] 1 3 5* 10* 7 6 p=5
l0 l1
r1 r0 r<=l
[5]a' 1 3 10bc' 5ab' 7 6 p=5c
r l quick(1,3); quick(5,7);
[5] 1 3* (5)* [10] 7 6°° p=5,10
l0 l1 l2 l3 l0 l1 l2
r1 r0 r1 r0 r<=l
[5]a' 1 5bc' 3ab' [10]d' 7 6dee'f' p=5c,10f
r l rl quick(1,2); quick(5,6)
[3] 1* (5)* (5) [6]° 7° (10) p=3,6
l0 l1 l2 l0 l1
r1 r0 r2 r1 r0 r<=l
[3]a' 5bc' 1ab' 5 7d'ef' [6]de' 10 p=3c,6f
^
|
hier wird die 7 mit 6 überschrieben überschrieben!
1 (3) (5) (5) (6) 6 10
^
|
hier sollte eigentlich die 7 stehen!
