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.

URL:         /axel/informatik2_ss01_blatt4.html
 
 

zusätzlicher Übungstermin Donnerstagsgruppe:             Mittwoch 23.5 16.00-18.00   S70
 

Aufgabe 9(4 Punkte)

Sortieren Sie das Wort BIGBROTHER mittels Countsort in ansteigende Reihenfolge. .
 
 

Aufgabe10 (10 Programmierpunkte - Abgabe per email bis 31.5.01 10.00 Uhr)

Schreiben Sie eine C Funktion mit dem Namen my_mergesort_matrikelnummer(), welche ein int-feld  mittels Mergesort sortiert.
Die Deklaration der Funktion ist:
                                                                        int my_mergesort_matrikelnummer(int *feld, int feld_laenge)

Der zweite Parameter ist die Anzahl der Einträge im zu sortierenden Feld. Beim Namen der Routine ist matrikelnummer durch eine Ihrer Matrikelnummern zu ersetzen. Verwenden Sie bei der Implementierung wie bei der Realisierung des 'mittel guten' Quicksort, bei dem immer das kleinere Feld zuerst  genommen wird, das vorhandene Feld zur Speicherung der einen Hälfte der Daten.
 

Aufgabe 11( 3+6 Punkte)
In der Vorlesung wurde ein C Programm zur Erstellung eine Baumes und für die 6 Durchlaufreihenfolgen vorgestellt.

a) Füllen Sie diesen Baum mit den 12 verschiedenen Zahlen, die Sie erhalten wenn Sie Ihre beiden 6-stelligen Matrikelnummern verknüpfen, und die danach eventuell doppelt vorkommenden Ziffern  solange verdoppeln bis sie eine Zahl erreichen, die noch nicht vorkommt. Zeichnen Sie die Schritte beim Füllen des Baumes auf.

b) Wie sind die Ausgaben bei den 6 verschiedenen Durchlaufreihenfolgen?
 
 
 

Aufgabe 12 (2+2+2 Punkte)
Ein Sortierverfahren heisst stabil, wenn bei gleichen Schlüsselwerten sich die Reihenfolge im Sortierverfahren nicht ändert. Welche der drei Verfahren Quicksort - Heapsort - Countsort ist stabil, welches nicht. Begründung. Spezifizieren Sie genau welches Quicksort Sie meinen.
Ein typischer Fall, bei dem Schlüsselwerte mehrfach vorkommen ist, wenn zusammengesetzte Daten vom Typ (wert,info) bezüglich wert sortiert werden. Dabei kann derselbe wert mit verschiedenen info-teilen auftreten. Hat man vorher schon bezüglich anderer Eigenschaften sortiert, so will man eventuell diese Reihenfolge innerhalb der Daten mit gleichem wert beibehalten, d.h. das Sortierverfahren muss stabil sein.