Hardware Reference
In-Depth Information
27
PBP
tmp,5B
28
29
4H
x,A,j
Element x hat seinen Platz gefunden
STO
30
ADDU
i,i,8
31
1H
CMP
tmp,i,size
32
PBN
tmp,2B
33
Kein Return-Wert
POP
0,0
Nun konnen wir uns dem Quicksort selbst zuwenden. Die Idee besteht darin,
aus dem zu sortierenden Bereich einen so genannten Pivot-Wert
pivot
aus-
zuwahlen
2
und die Elemente zunachst so umzusortieren, dass links von
pivot
nur Werte stehen, die kleiner sind als dieser Wert, und rechts nur Werte, die
großer sind. Die beiden Teilbereiche werden anschließend rekursiv nach dem
gleichen Verfahren sortiert. Insgesamt besteht der Algorithmus aus folgenden
Schritten [39]:
1. Wenn der zu sortierende Bereich weniger als
cutoff
Elemente enthalt, so
wird mit Insertion Sort sortiert. Ansonsten weiter mit Schritt 2. Der Wert
fur
cutoff
liegt typischerweise zwischen 4 und 20. Er kann in Zeile 25
eingestellt werden.
2. Wahle ein Pivot Element. Das Verfahren lauft um so besser, je besser das
hier gewahlte Element in der Mitte der zu sortierenden Zahlen liegt. Etwas
gunstiger als ein Element zufallig auszuwahlen erweist es sich, das Erste,
das letzte und das Element zu vergleichen, das in der Mitte des Bereichs
steht. Das mittlere davon wird der Pivot (Zeilen 31-70).
3. Nun wird der Sortierbereich durch Vertauschen von Elementen so partitio-
niert, dass alle Elemente links vom Pivot-Element (also die mit kleineren
Indizes) kleiner sind als dieses und alle rechts davon großer (Zeilen 72-87).
Dazu wird mit zwei Indizes gearbeitet. Der erste,
i
, bewegt sich vom unte-
ren Ende auf die Mitte zu und der zweite,
j
, vom oberen Ende her. Wird
links ein Element gefunden, das nach rechts gehort, und rechts eines, das
nach links muss, so werden die beiden vertauscht (Zeilen 83-87).
4. Jetzt wird dieses Verfahren fur den linken und rechten Teilbereich jeweils
rekursiv aufgerufen (Zeilen 92-99).
Fur ein Beispiel siehe etwa [39].
quicksort.mms
1
PREFIX :QSort:
2
∗
Parameter
2
Pivot bedeutet Drehachse, Drehpunkt, Drehzapfen oder Schwenkungspunkt.
