Aufgabe 1:  (Quicksort)

Analysieren Sie die Zeitkomplexität von Quicksort für den Fall, dass die Auf­teilung der Folge immer mindestens im Verhältnis 1:3 erfolgt (d.h. im Verhältnis 1:3 oder besser, bis hin zu 1:1).

Aufgabe 2:  (Quicksort)

Die Wahl des Vergleichselements x ist entscheidend für das Laufzeitverhalten von Quicksort. Implementieren Sie Quicksort in der Weise, dass Sie

1. als Vergleichselement x ein zufälliges Element der Eingabefolge wählen,
2. als Vergleichselement x den median of three wählen, also das der Größe nach mittlere Element von drei Elementen der Eingabefolge.

Untersuchen Sie, wie sich die Laufzeit von Quicksort gegenüber der ursprünglichen Implementierung verhält.

Aufgabe 3:  (Quicksort)

Das Sortierverfahren Insertionsort ist zwar im schlechtesten Fall mit Θ(n²) sehr langsam, aber im günstigsten Fall, wenn die Eingabefolge bereits sortiert ist, benötigt es nur Θ(n) Schritte. Auch bei annähernd sortierten Eingabefolgen ist Insertionsort sehr schnell.

Quicksort dagegen nimmt keine Rücksicht auf schon bestehende Vorsortierungen und benötigt auch für eine bereits sortierte Eingabefolge Θ(n·log(n)) Schritte.

Ändern Sie die Implementierung von Quicksort so, dass zu Beginn der Funktion quicksort geprüft wird, ob die zu behandelnde Eingabefolge bereits sortiert ist. In diesem Fall kann die Funktion mit return sofort verlassen werden. Somit entfallen weitere rekursive Aufrufe von dort aus.

Untersuchen Sie, wie sich die Laufzeit von Quicksort gegenüber der ursprünglichen Implementierung verhält

1. bei schon sortierten Folgen,
2. bei absteigend sortierten Folgen,
3. bei Zufallsfolgen, die nur wenige unterschiedliche Elemente enthalten (z.B. nur Zahlen zwischen 0 und 99),
4. bei Zufallsfolgen, die viele unterschiedliche Elemente enthalten.

Aufgabe 4:  (Quicksort)

Ändern Sie die Implementation der Funktion quicksort in der Weise, dass Sie als Vergleichselement x das letzte Element eines monoton ansteigenden Anfangsstücks der Eingabefolge wählen. Wenn beispielsweise die Eingabefolge 2 3 5 5 6 4 8 1 lautet, so steigt deren Anfangsstück bis zur 6 monoton an. Somit wird x = 6 als Vergleichselement gewählt. Die Suche von links nach dem ersten Element a_i mit a_ix kann dann bei dieser 6 beginnen, denn die vorhergehenden Elemente sind alle kleiner (oder auch gleich 6, was aber nicht schadet).

Zwei Sonderfälle sind zu behandeln, nämlich Eingabefolgen, bei denen x das erste oder das letzte Element ist. Im ersten Fall wählen wir x neu, und zwar als das mittlere Element der Eingabefolge, wie in der ursprünglichen Implementierung von Quicksort, um bei einer absteigend sortierten Eingabefolge quadratische Laufzeit zu vermeiden. Im zweiten Fall ist die Eingabefolge bereits sortiert, sodass wir die Funktion quicksort mit return verlassen können.

Implementieren Sie dieses Vorgehen in möglichst eleganter Weise. Stellen Sie dieselben Untersuchungen über die Laufzeit von Quicksort an wie in der vorigen Aufgabe.

Aufgabe 5:  (Quicksort)

Im schlechtesten Fall kommt bei Quicksort in jedem Rekursionsschritt eine ungünstige Auf­teilung der Folge zustande: Das eine Teilstück besteht nur aus einem Element, das andere aus dem Rest der Folge. Dies führt zu einer Zeitkomplexität von Θ(n²).

Schlimmer noch aber ist, dass die Rekursionstiefe Θ(n) beträgt. Schon bei n=10000 führt dies zu einem Absturz des Programms aufgrund von stack overflow.

Programmieren Sie eine Variante von Quicksort, in der Sie den zweiten der beiden rekursiven Aufrufe im Rahmen einer While-Schleife behandeln. Programmieren Sie das Verfahren so, dass stets das kürzere Teilstück rekursiv weiterbehandelt wird und das längere im Rahmen der While-Schleife abgearbeitet wird.

Durch diese Maßnahme verbessert sich zwar die Zeitkomplexität im schlechtesten Fall nicht, aber die Rekursionstiefe sinkt auf O(log(n)).

Aufgabe 6:  (Mergesort)

Ändern Sie die Version b der Funktion merge so ab, dass nur diejenigen Elemente in das Hilfsarray b ausgelagert werden, für die dies wirklich notwendig ist. Nicht notwendig ist es für alle Elemente a_i der vorderen Hälfte, die kleiner oder gleich dem ersten Element a_m+1 der hinteren Hälfte sind, denn diese werden anschließend wieder an ihren ursprünglichen Platz zurückkopiert.

Suchen Sie die Position des ersten Elements, das in das Hilfsarray ausgelagert werden muss, mit binärer Suche.

Analysieren Sie die Zeitkomplexität von Mergesort, wenn diese neue Version d der Funktion merge angewendet wird,

1. im günstigsten Fall
2. im schlechtesten Fall

Hinweis: Die Analyse lässt sich ähnlich durchführen wie bei der Funktion buildheap des Verfahrens Heapsort.

Aufgabe 7:  (Radixsort / Quicksort)

Kombinieren Sie die Sortierverfahren Radixsort und Quicksort zu einem Sortierverfahren Radixquicksort.

Das Verfahren Radixquicksort soll nichtnegative 32-Bit-Integer-Zahlen sortieren, die Funktionsweise soll folgende sein:

Im ersten Schritt wird das Auf­teilungsverfahren von Quicksort hinsichtlich des Bits an Bitposition 30 der Zahlen durchgeführt¹). Dabei kommen alle Zahlen mit einer 0 an Bitposition 30 in die linke Hälfte und alle Zahlen mit einer 1 an Bitposition 30 in die rechte Hälfte. Diese Hälften werden nun rekursiv nach Bit 29 sortiert usw.

Implementieren Sie das Verfahren Radixquicksort.

Analysieren Sie die Zeitkomplexität des Verfahrens.

Aufgabe 8:  (Shellsort)

In dem Originalartikel von D.L. Shell [She 59] wird die h-Folge

n div 2, n div 4, n div 8, ..., 1

verwendet. Welche Komplexität hat Shellsort mit dieser h-Folge im schlechtesten Fall? Geben Sie eine 0-1-Datenfolge an, die einen schlechtesten Fall darstellt.