Sortieren: Grobe Zusammenfassung der Grundlagen

Interne Sortierverfahren: (Direkter Zugriff auf jedes Einzelne Folgenelement)

- Sortieren durch direktes Einfügen

- Quicksort

- Heapsort

Externe Soriterverfahren:

Die zu sortierende Liste passt nicht ganz in den Hauptspeicher und wir haben deshalb KEINEN direkten Zugriff auf wirklich jedes einzelne Folgenelement.

Sortieren durch direktes Einfügen:

Wir betrachten nacheinander die Speicherplätze a[2] bis a[n] unseres Feldes. Jedes Element a[i] wird in der bereits sortierten Teilfolge a[1]…a[i-1] an richtigen Stelle eingefügt. Dabei wird i für jede Iteration um 1 erhöht, bis das ende des feldes erreicht wurde.

Wir bringen alle Bücher von links nach rechts im Regal fortschreitend an die richtige Position. Das erste Buch steht zunächst am richtigen Platz. Dann nehmen wir das zweite Buch hinzu und vertauschen es mi dem ersten, falls es links von diesen stehen muss. Dann nehmen wir das dritte buch hinzu, vertauschen es mit dem zweiten, falls nötig, und vertauschen es anschließend gegebenenfalls mit dem ersten. Dann nehmen wie das vierte Buch hinzu, usw.

Binäre Bäume –> Heaps und Heaptsort

In einem binären Baum hat ein Vaterknoten an Stelle i seine Kindknoten an den Stellen 2i und 2i+1.

Heapbedingung: Jeder Knoten muss kleiner sein als seine seine zwei Kindknoten. Oder anders ausgedrückt:

Eine Teilfolge von Schlüsselwerten kLi, kLi+1, … , kRe. (1 ≤ Li ≤ Re ≤n) heißt Heap, falls für alle i aus {Li, … Re] gilt:

k2i < ki falls 2i ≤ Re und k2i+1 < ki falls 2i+1 ≤Re

Heapsort

Heapsort beruht auf dem Vergleichen und Vertauschen von Schlüsselwerten. Zunächst muss die zu sortierende Zahlenfolge in einen Heap überführt werden. Hierbei nutzt man aus, dass die Blätter eines Baumes immer die Heapeigenschaft erfüllen. Durch Versickern der übrigen Elemente wirdein Ausgangsheap erzeugt.

Da die Wurzel eines Heaps immer der größte Knoten ist, in unserem Fall, vertauschen wir das erste und letzte Element der Liste. Das letzte Element ist jedzt an der richtigen Position und wird im Folgenden nicht mehr betrachtet.

Das neue erste Element wird daraufhin in den n-1 verbleibenden Zahlen versickert, um somit wieder einen Heap herzustellen.

Die Schritte der Vertauschens und das erneute versickerns werden immer abwechselnd durchgeführt, bis keine Zahlen mehr zu sortieren sind.

-       Ausgangsheap

-       i)  Erstes und letztes Element der Liste vertauschen

-       ii) Erneut Heap durch versickern erstellen

  • Wiederhohle i und ii abwechselnd, bis keine Zahlen mehr zu sortieren sind

Quicksort – Divide and Conquer

-       Gegeben sei die Folge S0 = (a[1] … a[n])

-       Setze das Pivotelement x0 = a[beliebeig]

  • Sonderfall 1: x0=a[1] (in java eigentlich a[0]) -> d.h. wähle immer das linke Element als Pivotelement.
    • Durchsuche die restliche Folge S0 (d.h. die Folge ohne Pivotelement ) von Links, bis ein Element a[i] > x0 gefunden ist oder der rechte Rand a[n] der Folge erreicht wurde
    • Dursuche dann die Folge S0 ohne Pivotelement von rechts, bis ein Element a[j] < x0gefunden wurde.
      • Falls i < j (beachte der Index! -> wir wisse schon durch das Vergleichen mit dem Pivotelement, das a[j] größer ist als a[i]), vertausche beide Elemente und seitze die Suche fort.
      • Falss i≥j -> vertausche a[j] und teile die Folge an dieser Stelle in die Teilfolgen
        • S1 = (a[1], .., a[j-1])
        • S2 = (a[j+1], … , a[n])
        • Sortiere die Teilfolgen analog zu S0
  • Sonderfall 2: x0 = a[n] (in java eigentlich a[n-1]) -> d.h. wähle immer das rechte Element als Pivotelement.