MathePrisma Logo

Sortierverfahren

Sortierverfahren

Quicksort

Simulation

Dieses Verfahren geht auf Hoare (1962) zurück. Es erreicht im Mittel die bestmögliche Zahl von Schlüsselvergleichen und Datensatzbewegungen.

Voraussetzung

Gegeben ist ein Feld A mit n Positionen, also A[0] ... A[n-1], in welches die zu sortierenden Datensätze eingetragen sind. Mittels A[i].Schluessel können wir auf den Schlüssel des i-ten Datensatzes zugreifen.

Die Idee


  1. Bringe einen Datensatz an die richtige Stelle, so dass zusätzlich links von ihm nur kleinere,
    rechts von ihm nur größere Schlüssel stehen.
  2. Sortiere dann mit der gleichen Methode
    zuerst den linken,
    dann den rechten Teilabschnitt (Rekursion).
Prinzip: Divide and Conquer (Teile und Herrsche)

Das Raffinierte


dabei ist die Art, wie man 1. erreicht:
  1. Nehme als Datensatz, der an die richtige Stelle eingefügt werden soll, den ganz links stehenden.
    Sein Schlüssel heiße s.
  2. Laufe von links über die Folge bis zur ersten Position i
    mit Schlüssel >= s.
    Laufe von rechts über die Folge bis zur ersten Position j
    mit Schlüssel <= s.
  3. Wenn i < j gilt,
    vertausche die Datensätze an den Positionen i und j und mache mit diesen Positionen in 2. weiter.
  4. Wenn dann irgendwann i >= j gilt,
    stehen links von j und an j nur Schlüssel <= s und
    rechts von j nur solche >= j.
    Vertausche also den Datensatz ganz links mit dem an Position j.

    Damit man in 2. beim Laufen von links nicht zu weit (d.h. aus der Folge heraus) läuft, muss am Anfang dafür gesorgt werden, dass s nicht der einzige größte Schlüssel ist.
    Dazu vertauscht man die Datensätze an den beiden Enden in dem Fall, dass der ganz links einen größeren Schlüssel besitzt als der ganz rechts.

Kein Mensch würde spontan so ein "Divide and Conquer" -Verfahren durchführen.

Um die Wirkungsweise zu verstehen, solltest du folgende Übung durchführen.

   Zur Übung genügt es, einen Schritt auszuführen, also ohne Rekursion.

Lege dazu Münzen in eine Reihe auf den Tisch.
Sortiere mit der beschriebenen "raffinierten" Methode die Münze ganz links an die richtige Position, so dass links nur Münzen kleineren Wertes, rechts nur solche größeren Wertes liegen.
Überzeuge dich, dass die Münze nun wirklich an der richtigen Position liegt.

(Du hast gerade keine Münzen da?)

Die Idee ist in folgendem Algorithmus präzisiert.

Der Algorithmus

Der Algorithmus


wenn A[0].Schluessel > A[n-1].Schluessel dann:
    vertausche A[0] mit A[n-1]
(jetzt ist A[0].Schluessel <= A[n-1].Schluessel)
wiederhole
   suche kleinstes i mit A[i].Schluessel > A[0].Schluessel
   suche größtes j mit A[j].Schluessel < A[0].Schluessel
   wenn i < j dann:
       vertausche A[i] und A[j]
   (es ist A[0].Schluessel >= alle Schlüssel in A[1] ... A[i] und
   A[0].Schluessel <= alle Schlüssel in A[j] ... A[n-1])
solange i < j
vertausche A[j] und A[0]
(es ist A[j].Schluessel >= alle Schlüssel in A[1] ... A[j-1]
 und A[j].Schluessel <= alle Schlüssel in A[j+1] ... A[n-1])
sortiere A[0] ... A[j-1] mit dem Algorithmus (Rekursion)
sortiere A[j+1] ... A[n-1] mit dem Algorithmus (Rekursion)