Abstrakt

Den Kern dieses Sortierverfahrens bildet die Partitionierung des zu sortierenden Arrays in zwei Teile, welche grob vorsortiert werden. Anschließend werden die beiden Teile nach dem gleichen Prinzip unabhängig für sich geordnet. Diese Verfeinerung hat eine größere Genauigkeit der Vorsortierung zur Folge. Letztendlich, bei sehr kleinen Teilmengen angekommen, ist diese exakt.

Als erstes wird aus der Menge ein beliebiges Element herausgegriffen, welches im folgenden als Pivotwert bezeichnet wird. Anschließend wird das Feld von links nach rechts nach Elementen durchsucht, die größer sind als der Pivotwert. Diese Werte gehören der Sortierordnung nach auf die andere Seite des Pivotwerts. Auf die gleiche Art und Weise wird die Menge auch von rechts nach links durchsucht, um Werte zu finden, welche kleiner als der Pivotwert sind. Implementierungstechnisch werden die gefundenen Werte einfach vertauscht. Nun wird die Menge in zwei Teilmengen zerlegt und die obigen Schritte auf diesen angewandt.

  1. Durch das Festlegen des Pivotwertes wird das Feld partitioniert.
  2. Nun werden Elemente, die größer als der Pivotwert sind und links von diesem liegen, gesucht.
  3. Desweiteren werden Elemente gesucht, die kleiner sind als der Pivotwert und rechts von diesem liegen.
  4. Wurden zwei Werte mit diesen Eigenschaften gefunden, werden sie vertauscht.
  5. Nun werden die Partitionen unabhängig voneinander nach dem gleichen Schema, beginnend bei Punkt 1 sortiert.
  6. Dieser Vorgang wiederholt sich, solange die Anzahl der Elemente in einer Partition größer als zwei ist.


Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Beispiel Aufwärts: Arbeitsweise Vorherige Seite: Arbeitsweise   Inhalt

2002-05-09