| procedure quicksort (l,r : integer); | ||
| var v,t,i,j: integer; | ||
| begin | ||
| if r > l then | ||
| begin | ||
| v:=a[r]; i:=l-1; j:=r; | ||
| repeat | ||
| repeat i:=i+1 until a[i]>=v; | ||
| repeat j:=j-1 until a[j]<=v; | ||
| t:=a[i]; a[i]:=a[j]; a[j]:=t; | ||
| until j<=i; | ||
| a[j]:=a[i]; a[i]:=a[r]; a[r]:=t; | ||
| quicksort(l,i-1); | ||
| quicksort(i+1,r); | ||
| end | ||
| end; | ||
|
Bei dieser Implementation dient die Variable v zur Speicherung des aktuellen Wertes des "zerlegenden Elements" a[i], während i und j der linke bzw. rechte Zeiger des Durchsuchens sind. Ein zusätzlicher Austausch von a[i] und a[j] mit j<i erfolgt unmittelbar nachdem sich die Zeiger treffen, doch bevor das Treffen festgestellt und die äußere repeat-Schleife verlassen wird. Die drei Zuweisungsbefehle, die nach dieser Schleife folgen, implementieren den Austausch von a[i] und a[j] (um das zusätzliche Austauschen rückgängig zu machen) sowie von a[i] und a[r] (um das zerlegende Element an die richtige Position zu setzen). |
|
| Zurück | |