procedure quicksort (l,r : integer);
  var i: integer;
  begin
  if r > l then
         begin
           i := partition(l,r);
          quicksort(l,i-1);
          quicksort(i+1,r);
          end
  end;

 

Die Parameter l und r begrenzen die Teildatei innerhalb der ursprünglichen Datei, die zu sortieren ist.

Das entscheidende Element der Methode ist die Prozedure partition, die das Feld so umordnen muß, daß die folgenden Bedingungen erfüllt sind:

 
Für ein beliebiges i befindet sich das Element a[i] an seinem endgültigen Platz im Feld
Alle Elemente in a[l],...,a[i-1] sind kleiner oder gleich a[i]
Alle Elemente in a[i+1],...,a[r] sind größer oder gleich a[i]
 

Dies kann leicht implementiert werden: Zuerst ist ein Element a[r] auszuwählen, das in seine endgültige Position gebracht werden soll. Dann sucht man das Feld von links beginnend durch, bis ein Element gefunden wird, das größer als a[r] ist, und sucht man das Feld von rechts beginnend durch, bis ein Element gefunden wird, das kleiner als a[r]ist.Die beiden Elemente, bei denen das Durchsuchen unterbrochen wurde, sollen ausgetauscht werden. Wenn man in dieser Weise fortfährt, ist gewährleistet,daß alle Elemente des Felds links vom linken Zeiger kleiner und alle Elemente des Felds vom rechten Zeiger größer als a[r] sind. Wenn sich die Zeiger treffen, ist der Zerlegungsprozeß nahezu beendet; soll nur a[r] mit dem am weitesten links befindlichen Element der rechten Teildatei vertauscht werden.
Zurück