Programmieren mit Oberon -POW!
Kapitel 9 - Sortieren
Einleitung
Ich möchte dieses Kapitel mit einem kleinen Experiment beginnen:Suchen Sie sich bitte einen kooperativen Partner (Dieser muss auch keine Vorkenntnisse besitzen.) und ein Kartenspiel, wobei auch Zahlenkarten o.a. gehen.
Legen Sie bitte aus dem gut gemischten Kartenstapel 7 bis 8 Karten in einer Reihe auf den Tisch.
Aufgabe: Lassen Sie die Karten unter der Bedingung sortieren, dass immer nur 2 Karten getauscht werden können und nur in einer Reihe liegen bleiben sollen.
1. Vergleichen Sie bitte aufmerksam das Vorgehen Ihres Partners mit dem Weg, den Sie gewählt hätten.
2. Diskutieren Sie die Methoden und versuchen Sie, noch einen weiteren Weg zu finden.
In einem Großteil der Fälle sortieren zwei verschiedene Personen spontan auf durch verschiedene Vorgehensweisen. Und zur weiteren Überraschung lassen sich nach kurzer Bedenkzeit weitere Verfahren finden!
Wie Ihnen sicherlich im Folgenden noch deutlich wird, verhalten sich diese Verfahren auch besonders bei großen Datenmengen auch unterschiedlich. Für das Landesamt für Stastistik dürfte es schon von Belang sein, ob ein Auftrag z.B. vor einer Wahl 1 Stunde oder 2 Tage in Anspruch nimmt! Wir verlangen im Alltag immer wieder nach sortierten Informationen. Beispiele dafür sind:
- Telefonbücher,
- Fahrpläne,
- Ranglisten,
- Adressbücher u.v.m..
Für das Sortieren von beliebigen Daten werden Computer eingesetzt, weil das Sortieren zwar eine einfache, aber mühsame Arbeit ist.
Vorbereitung der Lektion
An dieser möchte ich Ihnen ein Modul bereitstellen, dass die Erzeugung von Zufallszahlen übernimmt. Diese werden in einem Array abgelegt und können dann im Anschluss sortiert werden.
Einfache Sortierverfahren
Sortieren durch direktes Einfügen
Download
Sie können an dieser Stelle einen Brickfilm als Videodatei (Achtung Datei > 5 MB!) zur Demonstration des Verfahrens herunterladen.
Nehmen wir uns eine einfache Zahlenliste und bearbeiten diese mit diesem Algorithmus:
| 23 | 44 | 27 | 89 | 1 | 13 | 35 |
| 23 | 44 | 27 | 89 | 1 | 13 | 35 |
| 23 | 27 | 44 | 89 | 1 | 13 | 35 |
| 23 | 27 | 44 | 89 | 1 | 13 | 35 |
| 1 | 23 | 27 | 44 | 89 | 13 | 35 |
| 1 | 13 | 23 | 27 | 44 | 89 | 35 |
| 1 | 13 | 3 | 27 | 35 | 44 | 89 |
Wie sicherlich leicht zu bemerken war, sind die sortierten Teile gelb gehalten und das aktuelle Element (Was dann im nächsten Schritt eingefügt wird.) ist rot gekennzeichnet.
Sollte Ihnen der kleine Brickfilm für das Herunterladen zu umfangreich sein, möchte ich Ihnen hier noch eine Alternative anbieten:
Drucken Sie diese zwei Seiten auf etwas festerem Papier (Zeichenkarton) aus. Danach nur noch ausschneiden und in der nummerierten Reihenfolge zurechtlegen und zusammen tackern. Hier sehen Sie dann den Ablauf im Daumenkinoformat.
Markieren Sie das aktuelle Element wieder rot und den sortierten Teil gelb.
Auffallen sollte Ihnen hierbei aber auf alle Fälle, dass das direkte Einfügen auch nur schrittweise durch den Tausch benachbarter Elemente erfolgt.
Nach dieser ausführlichen Vorarbeit muss dieser Sortierverlauf nun natürlich als Algorithmus formuliert werden, damit eine Implementation erfolgen kann.
verbale Beschreibung |
Die zu sortierende Liste wird der Reihe nach bearbeitet und das jeweilige Element an die Stelle des sortierten Teils gesetzt, an die es dem Alphabet oder der Größe nach gehört. |
Struktogramm |
|
MODUL |
Als Prozedur in das o.g. Modul implementiert, ergibt sich: PROCEDURE direinf*; VAR aktuell, i, pos: INTEGER; BEGIN FOR i:= 0 TO n-1 DO aktuell:= sort[i]; pos:= i-1; WHILE ((pos >= 0) & (sort[pos] > aktuell)) DO sort[pos+1]:= sort[pos]; pos:= pos-1; sort[pos+1]:= aktuell; END; END; END direinf; |
Sortieren durch Auswahl
Download
Sie können an dieser Stelle einen weiteren Brickfilm als Videodatei (Achtung Datei > 5 MB!) zur Demonstration des Verfahrens herunterladen.
verbale Beschreibung
In der unsortierten Liste wird nach dem kleinsten Element gesucht und dieses mit dem ersten Element vertauscht. Die unsortierte Restliste wird nun wieder nach dem kleinsten Element durchsucht und mit dem zweiten getauscht usw.
Eränzen Sie das o.g. Modul durch eine entsprechende Prozedur.
Zur Übung sortieren Sie vielleicht die Buchstaben ihres Namens durch das Auswahlverfahren.
Sortieren durch Austausch
Für das Austauschverfahren stelle ich Ihnen die Materialien zum Selbstudium zur Verfügung:
verbale Beschreibung
Die Liste wird schrittweise durch das Austauschen benachbarter Elemente bearbeitet, bis im ersten Durchlauf das größte Element am Ende der Liste steht, im zweiten Durchlauf das zweitgrößte Element an vorletzter Stelle usw..
Struktogramm
Download
Sie können an dieser Stelle einen weiteren Brickfilm als Videodatei (Achtung Datei > 7 MB!) zur Demonstration des Verfahrens herunterladen.
Höhere Sortierverfahren
Informieren Sie sich mit Hilfe des Demo-Programms CUM über höhere Sortierverfahren.
Nutzen Sie für Ihr weiteres Studium auch andere Quellen wie z.B. Wikipedia oder die Internetauftritte einiger Hochschulen.
Effizienz
Niedere Sortierverfahren (direktes Einfügen, Auswahl- und Austauschsortieren) sind durch eine zeitliche Effizienz von t(n) ~ n² gekennzeichnet.
Höhere Sortierverfahren wie z.B. Quicksort haben eine zeitliche Effizienz von t(n) ~ n*ln(n) aufzuweisen.
Annahme: 1000 Elemente werden in 1s sortiert.
Dann benötigt man für 100.000 Elemente mit einem
a) niederen Verfahren: 10.000s = 2h 46min 40s,
b) höheren Verfahren: 461s = 7min 41s.
© 2003 by Jörg Langenau