QuickSort

QuickSort ist ein Sortier-Algorithmus. Er heißt zu Recht QuickSort, denn er ist im Normalfall wohl der schnellste existierende Sortieralgorithmus, da er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt.

• Sehr kurze innere Schleife.
• Läuft am Ort („in-place“) ab, d.h. nur ein kleiner Hilfsstapel wird verwendet.
• Im Mittel benötigt Quicksort für das Sortieren von N Elementen nur 2N*ln(N) Vergleiche.

• Extrem störanfällig. Schon kleine Eingriffe oder Fehler bei der Implementation können das Verfahren stark verlangsamen oder sogar in eine Endlosschleife verwandeln.
• Quicksort ist für eine große Anzahl zu sortierender Elemente zwar sehr schnell, allerdings ist seine Leistung bei kleinen eher schwach.
• Im schlimmsten Fall, wenn immer das größte Element als Vergleichselement gewählt wird, benötigt Quicksort zum Sortieren von N Elementen N² Operationen, Quicksort wird zum „Slowsort“.

Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

Anschließend muss man also nur noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.

Die Längen der Teillisten ergeben sich aus der Wahl des Pivotelements. Idealerweise wählt man das Pivot so, dass sich zwei etwa gleich lange Listen ergeben, dann arbeitet Quicksort am effizientesten. Es sollte also etwa gleich viele Elemente kleiner als das Pivot und größer als das Pivot geben.

  funktion quicksort(links, rechts)
      falls links < rechts dann
          teiler := teile(links, rechts)
          quicksort(links, teiler-1)
          quicksort(teiler+1, rechts)
      ende
  ende