Universität Ulm,
Fakultät für Mathematik und Wirtschaftswissenschaften,
SAI
3. Uebungsblatt (03.11.98 - 10.11.98)
4. Aufgabe (10 Punkte)
Sie sitzen spät abends an der Bar und grübeln über ihrem gerade wieder
leer gewordenen Glas. Verzweifelt versuchen sie, die Trümmer ihrer
Informatikkenntnisse aus den ersten beiden Semestern zu sortieren.
"Quicksort, Bubblesort, Urlaubsort,..", sinnieren sie.
"Das Leben ist ein einziges Auf und Ab", sagt der Barmann tröstend,
der gerade einen Martini für ihren -
in letzter Zeit etwas seltsam gewordenen Freund 007 schüttelt.
Da kommt ihnen eine Idee. Sie werfen dem Barmann einen abgegriffenen
30 DM-Schein hin, warten nicht auf das Wechselgeld, torkeln zum heimischen
Schreibtisch - und: erfinden den Shakersort.
Da sie seit der Trennung von ihrer Freundin einen leichten Zug zum
Selbstquälen haben, entschliessen sie sich, den Algorithmus in einem
C-Programm zu implementieren, das (maximal 3000) Zahlen von der
Standardeingabe liest und anschliessend shakermässig sortiert und ausgibt.
Der schnöden Ordnung
zuliebe beschliessen sie grosszügig die Verwendung von Funktionen, die
ihr Programm übersichtlich machen. An der Prozedur
void shakersort(int tosort[], int num), die ihnen num eingelesene
Zahlen im Array tosort sortiert, kommen selbst sie nicht vorbei...
Hier nun der von ihnen erfundene Algorithmus für den Shakersort:
Die Zahlen im Array a[] ablegen. Vom Anfang bis zum Ende des Arrays
laufen - immer die aktuelle Zahl
a[i] mit deren Nachfolger
a[i+1] vergleichen - ist a[i+1] kleiner, werden die beiden
getauscht - am Ende des Arrays rückwärts laufen - a[i] mit
a[i-1] vergleichen - ist a[i] kleiner,
werden beide getauscht - dieses Auf und Ab solange durchführen, bis
bei einem Durchgang nichts mehr getauscht wurde - fertig sortiert!
Viel Spass!
Martina Maier, 2. November 1998