Aufgaben

Aufgabe: Quick Sort dokumentieren

Welche Aufrufe von partition werden beim Aufruf von quick_sort(a) mit a = [3,2,1,6,7,4,8,5] in welcher Reihenfolge ausgeführt? Geben Sie an, welchen Wert a vor und nach jedem Aufruf von partition hat.

Aufgabe: Einfache Prozedur zum Sortieren analysieren

Betrachten Sie die folgende Definition in Python.

def simple_sort(a):             #0
  for i in range(0, len(a)):    #1
    for j in range(0, len(a)):  #2
      if a[i] < a[j]:           #3
        swap(a, i, j)           #4

1. Verwenden Sie korrekte Fachsprache um die gezeigte Definition zu beschreiben.
2. Dokumentieren Sie die Ausführung des Aufrufs simple_sort([2,1,3]) mit Hilfe einer Programmtabelle, die auch eine Spalte für den Parameter a enthält.
3. Beschreiben Sie den Effekt eines Aufrufs von simple_sort mit einer Liste von Zahlen.
4. Beschreiben Sie die Laufzeit von simple_sort mit Hilfe der O-Notation.
5. Welche der folgenden Aussagen treffen zu?
   • Die Anzahl der bei einem Aufruf von simple_sort ausgeführten Vergleiche hängt nicht von der Reihenfolge der Elemente in der übergebenen Liste ab.
   • Jedes Paar von Indizes führt zu zwei Vergleichen.
   • Direkt nach jedem Durchlauf der äußeren Schleife
     • steht das größte Element der gesamten Liste an Index i.
     • ist der Bereich bis zum Index i aufsteigend sortiert.

Aufgabe: Merge-Sort Funktion implementieren

In dieser Aufgabe lernen Sie ein Sortierverfahren kennen, dessen Laufzeit auch im worst case in \(O(n\cdot log_{2}(n))\) ist. Dieses Verfahren verwendet wie Quick Sort zwei rekursive Aufrufe zum Sortieren von Teillisten, stellt aber sicher, dass sich dabei die Listen-Größen unabhängig von den Listen-Elementen halbieren, wodurch logarithmische Rekursionstiefe garantiert wird.

Intuitiv können wir das Verfahren wie folgt beschreiben:

1. Teile die Eingabe-Liste in zwei Hälften und sortiere diese rekursiv.

2. Durchlaufe dann die sortierten Hälften und füge sie zu einer Liste zusammen, dass alle Elemente in sortierter Reihenfolge enthält.

Die rekursiven Aufrufe verfahren nach dem selben Prinzip. Für die Eingabe [3,2,1,6,7,4,8,5] ergeben sich also die folgenden Zwischenschritte. Hierbei fassen wir Operationen auf gleicher Rekursionstiefe zusammen. Bei dieser Liste der Größe acht ergeben sich also drei Schritte.

• [3,2,1,6,7,4,8,5]
• [2,3,1,6,4,7,5,8]
• [1,2,3,6,4,5,7,8]
• [1,2,3,4,5,6,7,8]

Definieren Sie eine rekursive python-Funktion (keine Prozedur) merge_sort, die das Merge Sort Verfahren implementiert. Die Eingabe-Liste soll von dieser Funktion nicht verändert werden.¹ Nach zwei rekursiven Aufrufen sollen die sortierten Hälften zusammengefügt werden. Definieren Sie dazu eine Funktion merge mit zwei Listen als Parametern, die als Ergebnis eine sortierte Liste mit den Elementen beider Parameter zurück liefert.

Untersuchen Sie Ihre Implementierung experimentell. Wie verhalten sich die Laufzeiten in Abhängigkeit von der Eingabegröße?

Bonusaufgabe: Heap-Sort Prozedur implementieren

Von den besprochenen effizienten Sortierverfahren hat Quick Sort den Vorteil, dass keine neue Liste angelegt werden muss und den Nachteil, dass die Laufzeit im schlechtesten Fall quadratisch ist. Andererseits ist es nicht leicht, Merge Sort zu implementieren, ohne eine neue Liste anzulegen. Dafür ist die Laufzeit auch im schlechtesten Fall in \(O(n\cdot log(n))\).

In dieser Aufgabe sollen Sie ein Sortierverfahren implementieren, dass beide Vorteile vereint. Die Idee dazu ist eine Variante von Max Sort, die wir in mehreren Schritten entwickeln.

Max Sort sortiert eine Liste so, dass die Liste zu jeder Zeit aus einem unsortierten (vorderen) und einem sortierten (hinteren) Bereich besteht. Der sortierte Bereich wird dabei schrittweise vergrößert, indem das größte Element des unsortierten Bereiches an die Grenze getauscht wird.

Die Grundidee von Heap Sort ist es, den unsortierten Bereich so zu strukturieren, dass das größte Element des unsortierten Bereichs schneller gefunden werden kann als bei Max Sort. In jedem Schritt wird dabei nur logarithmischer Aufwand nötig sein, das größte Element zu finden und die dazu nötige Struktur aufrecht zu erhalten.

Wenn der unsortierte Bereich sortiert wäre, wäre es einfach, das größte Element zu finden. Den unsortierten Bereich zu sortieren ist ja aber gerade das Ziel eines Sortieralgorithmus - als Zwischenschritt zum Auffinden des größten Elementes wäre es zu aufwändig. Interessanter Weise gibt es eine andere Art, den unsortierten Bereich so zu strukturieren, dass man das größte Element einfach finden kann, und diese Art der Strukturierung ist weniger aufwändig als eine Sortierung.

Heaps

Die Heap-Datenstruktur ordnet enthaltene Einträge in einer Baumstruktur an. Ein Heap mit Zahlen als Einträgen ist entweder eine Zahl (in dem Fall enthält der Heap genau eine Zahl) oder eine Verzweigung, die eine Zahl als Beschriftung enthält und links und rechts davon Heaps als Kindknoten enthalten kann. Wir können die Baumstruktur durch Klammern kenntlich machen. Hier ist ein Beispiel für einen Heap in dieser Schreibweise.

(((2 17 7) 19 3) 100 (25 36 1))

Zeichnen Sie diesen Heap als Baum und betrachten Sie seine Ebenen: Die erste Ebene enthält die Wurzel des Baumes, die zweite Ebene die Beschriftungen der Kindknoten der Wurzel und so weiter.

Zusätzlich müssen Heaps die folgenden Eigenschaften erfüllen:

• Die Beschriftung eines Knotens ist nicht kleiner als die Beschriftungen seiner Kindknoten, sofern welche vorhanden sind.
• Alle Ebenen bis auf die unterste sind vollständig. Nur bei Knoten der beiden untersten Ebenen fehlen also Kindknoten.
• Die unterste Ebene ist von links nach rechts besetzt. Sobald von links nach rechts betrachtet ein Knoten fehlt, folgt kein weiterer Kindknoten der vorletzten Ebene.

Die erste Eigenschaft hat zur Folge, dass das größte Element an der Wurzel des Heaps steht. Die beiden anderen Eigenschaften haben zur Folge, dass der Heap auf eindeutige Weise aus einer Auflistung seiner Einträge in sogenannter Ebenenordnung rekonstruiert werden kann. Eine solche Auflistung der Einträge des oben gezeigten Heaps sieht wie folgt aus.

100 19 36 17 3 25 1 2 7

Der einzige Eintrag der ersten Ebene ist die Beschriftung der Wurzel des Heaps, also 100. Danach folgen die Beschriftungen der Kinder des Wurzelknotens, nämlich 19 und 36. Anschließend werden die Beschriftungen der dritten Ebene, nämlich 17, 3, 25 und 1 von links nach rechts aufgelistet. Die vierte Ebene ist nicht vollständig besetzt und enthält ganz links die beiden Einträge 2 und 7. Wie man sieht, steht der größte Eintrag ganz vorne. Eine umgekehrt sortierte Auflistung der Elemente würde ebenfalls einem Heap entsprechen. Um die Heap-Eigenschaften zu erfüllen ist es aber nicht notwendig, dass die Einträge in Ebenenordnung vollständig sortiert sind.

Die Auflistung der Einträge eines Heaps in Ebenenordnung erlaubt es, einen Heap als Liste darzustellen. Der gezeigte Heap kann dementsprechend wie folgt in python dargestellt werden.

[100,19,36,17,3,25,1,2,7]

Diese Reihenfolge erlaubt es, die Positionen der Listen-Einträge mit der besprochenen Baumstruktur in Beziehung zu setzen. Wenn \(p\) die Position eines inneren Knotens ist, ist \(2p+1\) die Beschriftung seines linken und \(2p+2\) die Beschriftung seines rechten Kindknotens. Zum Beispiel steht die Beschriftung 100 der Wurzel des Heaps an Position 0. An der Position \(2\cdot 0+1 = 1\) steht die 19, die Beschriftung des linken Kindknotens der Wurzel. An Position \(2\cdot0+2 = 2\) steht die 36, also die Beschriftung des rechten Kindes der Wurzel. Das linke Kind der 19 an Position \(1\) ist die 17 an Position \(2\cdot 1+1 = 3\); das rechte Kind der 17 an Position \(3\) ist die 7 an Position \(2\cdot 3+2 = 8\).

Funktionen auf Heaps programmieren

Schreiben Sie python-Funktionen left_child und right_child, die eine Position als Argument erwarten und die Position des linken bzw. rechten Kindknotens zurück liefern. left_child(1) soll also zum Beispiel 3 zurück liefern, und right_child(3) soll 8 zurück liefern.

Um eine unstrukturierte Liste in die Darstellung eines Heaps zu transformieren, müssen die Elemente so umsortiert werden, dass der der Liste entsprechende Heap alle Heap-Eigenschaften erfüllt. Die zweite und dritte Eigenschaft dienten nur der eindeutigen Darstellung als Liste. Aber die Eigenschaft, dass die Beschriftung der Wurzel nicht kleiner ist als die der Kindknoten der Wurzel kann in einer unstrukturierten Liste verletzt sein.

Zunächst beschäftigen wir uns damit, wie wir die Heap-Struktur aufrecht erhalten können, wenn die erste Heap-Eigenschaft nur an der Wurzel verletzt ist. Ein solcher Heap ist hier gezeigt:

((2 19 17) 7 3)

In diesem Heap erfüllen die Kindknoten die erste Heap-Eigenschaft, denn die 19 ist größer als die 2 und die 17, und die 3 hat keine Kindknoten. An der Wurzel ist die Eigenschaft allerdings verletzt, denn die 7 ist kleiner als die 19.

Um den Heap zu reparieren, können wir die Beschriftung 7 der Wurzel mit dem Maximum der Beschriftungen der Kindknoten tauschen. Dadurch ergibt sich der folgende Heap.

((2 7 17) 19 3)

Durch den Tausch ist nun die Heap-Eigenschaft am linken Kindknoten der Wurzel verletzt. Wir können das beschriebene Verfahren rekursiv auf diesen Kindknoten anwenden, um die entstandene Verletzung der Heap-Eigenschaft zu reparieren. Dadurch wird die 7 mit der 17 vertauscht, so dass sich der folgende Heap ergibt.

((2 17 7) 19 3)

Dieser Heap verletzt nun keine Heap-Eigenschaft mehr, da die 7 keine Kindknoten hat.

Definieren Sie eine rekursive Prozedur repair die das beschriebene Verfahren für Heaps in Listen-Darstellung implementiert. Die Prozedur soll drei Argumente erwarten:

• Die Liste, die den dargestellten Heap enthält
• Die Position der Wurzel des Heaps, an der die Heap-Eigenschaft verletzt sein könnte
• Die Größe des Heaps als Obergrenze für gültige Positionen

Der Effekt eines Aufrufs repair(a,root,size) soll sein, dass der Heap nach dem Aufruf die erste Heap-Eigenschaft erfüllt wenn sie vorher höchstens an der Wurzel verletzt war. Die übergebene Position der Wurzel erlaubt es, die Prozedur auch für Kindknoten aufzurufen. Die übergebene Obergrenze erlaubt es, zu testen, ob die Wurzel Kindknoten hat.

Um die definierte Prozedur anwenden zu können, muss sichergestellt sein, dass die erste Heap-Eigenschaft nur an der Wurzel verletzt ist. Wir müssen sie also von unten nach oben (in Listen-Darstellung also von hinten nach vorne) anwenden, um eine komplett unstrukturierte Liste in einen Heap umzuwandeln.

Definieren Sie eine Prozedur make_heap, die eine unstrukturierte Liste in einen Heap umwandelt. Die Prozedur soll als Argument eine unstrukturierte Liste erwarten und als Effekt dieses in einen Heap umwandeln, indem Schrittweise die Prozedur repair aufgerufen wird.

Heap Sort programmieren

Wir können nun mit Hilfe der definierten Prozeduren den Heap Sort Algorithmus implementieren. Dieser wandelt zunächst die übergebene Liste in einen Heap um. Anschließend wird wie bei Max Sort das größte Element des unsortierten Bereichs (das wegen der Heap-Eigenschaft an Position 0 steht) an die Grenze zum sortierten Bereich getauscht, der sich dadurch schrittweise vergrößert. Durch den Tausch kann die Heap-Eigenschaft nun an der Wurzel des Heaps, der den unsortierten Bereich darstellt, verletzt sein, was gegebenefalls vor dem nächsten Schritt des Algorithmus repariert werden muss.

Definieren Sie eine Prozedur heap_sort, die diesen Algorithmus implementiert. Als Argument soll die Prozedur eine unstrukturierte Liste erwarten und als Effekt diese Liste sortieren.