TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 39

Wie müssten Sie den Algorithmus Quicksort adaptieren, damit eine beliebige Eingabefolge absteigend sortiert wird? Schreiben Sie den Pseudocode für Ihren veränderten Algorithmus und führen Sie ihn mit der folgenden Eingabefolge durch:

<40,60,10,30,100,20,5,70>

Stellen Sie die Daten nach jedem rekursiven Aufruf dar. Markieren Sie jeweils die Datenelemente, deren Position sich verändert haben, und zusätzlich (z.B. in einer anderen Farbe) das Datenelement (Pivotelement), das an seine endgültige Position verschoben wurde.

Änderung am Pseudocode

In Zeile 5 wurde das größer-gleich in ein kleiner-gleich umgewandelt. In Zeile 8 wurde das kleiner-gleich nach dem ODER in ein größer-gleich umgewandelt.

Partition(var A,l,r,x)
i = l - 1; j = r; 
Wiederhole
  Wiederhole
    i = i + 1;
  bis A[i].key $\leq$ x;
  wiederhole
    j = j - 1;
  bis j $\leq$ ODER A[i].key $\geq$ x;
  falls i < j dann {
    vertausche A[i] mit A[j];
  }
bis i $\geq$

Beispielfolge

Das Pivotelement wird jeweils fett markiert und die Datenelemente deren Position verändert wurden kursiv. Fett und kursive Elemente sind Pivotelemente die an ihrer endgültigen Position sind.

40,60,10,30,100,20,5,70

100,70,10,30,40,20,5,60

100,70,10,30,40,20,5,60

100,70,60,30,40,20,5,10

100,70,60,30,40,20,50,5

100,70,60,30,40,20,5

100,70,60,40,30,20,5

100,70,60,40,30,20,5

Voilá, Folge sortiert!