Aufgaben

 aufwärts

Aufgabe 1:  (Quicksort)

Analysieren Sie die Zeit­komplexität von Quicksort für den Fall, dass die Aufteilung 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 Vergleichs­elements x ist entscheidend für das Laufzeit­verhalten von Quicksort. Implementieren Sie Quicksort in der Weise, dass Sie

  1. als Vergleichs­element x ein zufälliges Element der Eingabefolge wählen,
  2. als Vergleichs­element 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üng­lichen Implementierung verhält.

Aufgabe 3:  (Quicksort)

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

Quicksort dagegen nimmt keine Rücksicht auf schon bestehende Vor­sortierungen 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üng­lichen Implementierung verhält

  1. bei schon sortierten Folgen,
  2. bei absteigend sortierten Folgen,
  3. bei Zufalls­folgen, die nur wenige unter­schiedliche Elemente enthalten (z.B. nur Zahlen zwischen 0 und 99),
  4. bei Zufalls­folgen, die viele unter­schiedliche Elemente enthalten.

Aufgabe 4:  (Quicksort)

Ändern Sie die Implementation der Funktion quicksort in der Weise, dass Sie als Vergleichs­element x das letzte Element eines monoton ansteigenden Anfangs­stücks der Eingabefolge wählen. Wenn beispiels­weise 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 Vergleichs­element gewählt. Die Suche von links nach dem ersten Element ai mit aigrößer gleichx kann dann bei dieser 6 beginnen, denn die vorher­gehenden Elemente sind alle kleiner (oder auch gleich 6, was aber nicht schadet).

Zwei Sonderfälle sind zu behandeln, nämlich Eingabe­folgen, 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üng­lichen Implementierung von Quicksort, um bei einer absteigend sortierten Eingabefolge quadratische Laufzeit zu vermeiden. Im zweiten Fall ist die Eingabefolge bereits sortiert, so dass wir die Funktion quicksort mit return verlassen können.

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

Aufgabe 5:  (Quicksort)

Im schlechtesten Fall kommt bei Quicksort in jedem Rekursions­schritt eine ungünstige Aufteilung der Folge zustande: Das eine Teilstück besteht nur aus einem Element, das andere aus dem Rest der Folge. Dies führt zu einer Zeit­komplexität von Θ(n2).

Schlimmer noch aber ist, dass die Rekursions­tiefe Θ(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 Zeit­komplexität im schlechtesten Fall nicht, aber die Rekursions­tiefe 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 ai der vorderen Hälfte, die kleiner oder gleich dem ersten Element am+1 der hinteren Hälfte sind, denn diese werden anschließend wieder an ihren ursprüng­lichen Platz zurück­kopiert.

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

Analysieren Sie die Zeit­komplexitä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 Sortier­verfahren Radixsort und Quicksort zu einem Sortier­verfahren Radixquicksort.

Das Verfahren Radixquicksort soll nicht­negative 32-Bit-Integer-Zahlen sortieren, die Funktions­weise soll folgende sein:

Im ersten Schritt wird das Aufteilungs­verfahren von Quicksort hinsichtlich des Bits an Bitposition 30 der Zahlen durchgeführt1). 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 Zeit­komplexität des Verfahrens.

Aufgabe 8:  (Shellsort)

In dem Original­artikel 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.


1)  Bit 30 ist das signifikanteste Bit bei nicht­negativen ganzen Zahlen, Bit 31 ist immer 0.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.12.2002   Updated: 29.05.2016
Valid HTML 4.01 Transitional