Prof. Dr. R. Laue                                                                                                                                  SS01
                                Informatik II
                                Übungsblatt 11
                                            Abgabe: 19.7.01 in der Vorlesung
URL:         /axel/informatik2_ss01_blatt11.html
 
 

Die Aufgaben sollen in Zweiergruppen bearbeitet werden. Dreiergruppen sind nicht zulässig.
Jede Aufgabe soll  auf einem Extrablatt bearbeitet werden. Bitte auf jedem Blatt Name/Matrikelnummer notieren.
 

Werbung: Linux Blockkurs
 
 

Aufgabe 30 Bucketsort (6 Punkte)
Wählen Sie die Nachnamen von 3 Ministerpräsidenten der Bundesrepublik Deutschland aus. Nehmen Sie noch Ihre beiden Vornamen dazu. Führen Sie mit diesen 5 Namen das Bucketsort incl Präprozessing durch. Erläutern Sie die einzelnen Schritte.

Aufgabe 31 Bucketsort (4 Punkte)
Wie kann der Bucketsort Algorithmus variiert werden, damit Zahlen in ihrer natürlichen Reihenfolge sortiert werden.
Beispiel: Die Zahl 2345 wird dabei von Bucketsort als Zeichenkette der Länge 4 gesehen, sie soll nach dem Sortieren nach der Zahl 33 und vor der Zahl 11111 kommen.

Aufgabe 32( 3 Punkte)
Beweisen Sie folgende Formel (Hybridsort, Vorlesung)

h2 B(n,h) = n (n-1) B(n-2 , h-2) + n B(n-1, h-1)

dabei bezeichnet B(n,k) den üblichen Binomialkoeffizienten.