Komponenten" verschiedene Sortierverfahren kennengelernt und im VB.NET in einem Projekt, das bewertet wurde, umgesetzt. Daher werde ich diesen Monat über die mir bekannten Sortierverfahren schreiben und das in der Schule gemachte Projekt vorstellen.
Sortierverfahren
Ein Sortierverfahren ist ein Algorithmus, dessen Ziel es ist, ein Array zu sortieren. Die einzige Voraussetzung ist, dass auf der Menge der Elemente eine Ordnung definiert ist, z. B. die numerische Ordnung von Zahlen. Im Laufe der Zeit wurden viele verschiedene Sortierverfahren entwickelt, die unterschiedlich effizient arbeiten bezüglich der Zeitkomplexität (Anzahl der nötigen Operationen) und der Platzkomplexität (zusätzlich benötigter Speicherplatz). Je nach Sortierverfahren hängt die Zeitkomplexität von der Anordnung der Werte am Anfang ab, es wird dann zwischen Best Case, Average Case und Worst Case unterschieden. Beim Worst Case sind die Werte zu Beginn am schlechtesten vorgeordnet. Des Weiteren spielen bei der Zeitkomplexität die Zugriffszeiten auf Dateien eine Rolle. Die Platzkomplexität hängt unter anderem von der Größe des Arbeitsspeichers ab.
Daneben unterscheidet man noch zwischen stabilen und instabilen Sortierverfahren. Bei stabilen Sortierverfahren wird die relative Reihenfolge von Elementen, die bezüglich der Ordnung gleichwertig sind nicht verändert, bei instabilen Sortierverfahren wird dies allerdings nicht garantiert.
Verschiedene Sortierverfahren:
Hier möchte ich nun auf die vier verschiedenen Sortierverfahren, die ich in der Schule kennengelernt habe, eingehen. Zu einigen dieser Sortierverfahren, habe ich ein Strucktogramm erstellt, welches als Entwurf diente und den Ablauf detailliert darstellt.
Der Bubble-Sort ist einer von 4 Sortieralgorithmen, die ich in der Schule kennengelernt habe. Er ist der am wenigsten komplexe Algorithmus und auch der langsamste. Der Bubble-Sort ist ein stabiles Sortierverfahren.
Funktion:
Der Bubble-Sort durchläuft die Eingabe-Liste von links nach rechts und vergleicht hierbei jeweils die zwei nebeneinander liegenden Elemente. Sollten diese das Sortierkriterium verletzten, werden sie getauscht, danach geht der Algorithmus weiter zum nächsten. Ist der Algorithmus am Schluss der Liste angekommen, ist das grösste Element der gesamten Eingabe-Liste am Schluss. Danach wird der Vorgang so oft wiederholt, bis die Elemente komplett sortiert sind, dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es schon an der richtigen Stelle steht.
Strucktogramm - Bubble-Sort:
2. Ripple-Sort
Der Ripple-Sort ist eine optimierte Form vom Bubble-Sort. Der einzige Unterschied zum Bubble-Sort ist, dass der Ripple-Sort bei jedem Durchgang einen booleschen Wert auf "wahr" setzt, wenn etwas getauscht wurde. Ist dies nicht der Fall, bricht der Algorithmus ab und die Liste ist somit fertig sortiert. In der untenstehenden Animation sieht man, dass der Algorithmus vom Ripple-Sort nur sechs Mal durchläuft, wobei der Bubble-Sort noch ein siebtes Mal durchgelaufen wäre und am Schluss noch die 1 mit der 2, die beide schon am korrekten Platz sind, miteinander verglichen hätte.
![]() |
Ripple-Sort |
3. Intern-Sort:
Der Intern-Sort ist schon etwas komplizierter, aber auch schneller als die beiden vorher. Dieser Algorithmus sucht sich in der Eingabe-Liste den kleinsten Wert heraus. Dies macht er, indem er zuerst das erste Element der Liste mit dem größt möglichen (ÿ) vergleicht. Ist der Wert kleiner, werden dessen Position sowie das Element selber als kleinstes der Liste gespeichert. Danach geht er zum nächsten Element und vergleicht dieses nun mit dem Element, das vorhin abgespeichert wurde. Ist das neue Element wieder kleiner, wird nun dieses gespeichert. Dies geschieht solange, bis der Algorithmus einmal durch die ganze Eingabe-Liste gegangen ist und somit den kleinsten Wert ermittelt hat. Dieser kleinste Wert wird nun als erster in der Ausgabe-Liste (anhand der gespeicherten Position) gespeichert und in der Eingabe-Liste mit dem grössten Wert (ÿ) überschrieben. Dieser Ablauf geht solange weiter, bis die Ausgabe-Liste gleich lang wie die Eingabe-Liste ist.
Strucktogramm - Intern-Sort:
4. Quick-Sort:
Der Quicksort war das komplexeste Sortierverfahren zum Umsetzten, jedoch auch mit Abstand das schnellste Verfahren. Der Quick-Sort ist ein nicht-stabiler Sortieralgorithmus. Er hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt, was die Ausführungsgeschwindigkeit stark erhöht. Speziell an diesem Algorithmus ist, dass er sich selber mehrmals aufruft.
Funktion:
Als erstes wird aus der Eingabe-Liste genau das Element in der Mitte bestimmt und unterteilt somit die Liste in zwei Teillisten. Die Elemente der linken und der rechten Teilliste werden mit dem vorher bestimmten Element verglichen. Sind die verglichenen Elemente jetzt grösser (bzw. kleiner) als das Element in der Mitte, werden die beiden Elemente aus den Teillisten vertauscht. Das geschieht solange, bis jedes Element der Teilliste mit dem Element in der Mitte verglichen worden ist. Nun ruft sich der Algorithmus selbst auf und bestimmt wieder das Element in der Mitte, diesmal aber von den beiden Teillisten und unterteilt sie in weitere Teillisten. Das geht solange weiter, bis die Eingabe-Liste sortiert wurde.
Strucktogramm - Quick-Sort:
Das Projekt
Für das Projekt hatten wir etwa die Hälfte des Semesters Zeit, davor beschäftigten wir uns noch ausgiebig mit Strucktogrammen. Die Vorgaben des Programms waren folgende:
- Zeichensortierung: Bubble-Sort, Ripple-Sort, Intern-Sort & Quick-Sort
- Umlautfunktion - (ä kommt nach a und nicht am Schluss der Liste)
- Menubar - Funktionen: Datei, Bearbeiten, Farbe, Info
- Toolbar - Funktionen: Datei, Bearbeiten, Farbe, Info
- dynamische Menu- und Toolbar, (Clipboard-Handling)
- GUI: Optionen, Checkbox(+Menu), Sortierzeit, ShortCut,
- Wortsortierung 2 Algorithmen mit und ohne Umlaut
- Änderungsfreundlichkeit:(Trennung Formular/Sortiermodul, Option Compare Text Modul)
- Änderungsfreundlichkeit: Kommentare
- Zusatz: Selbsterarbeitete weitere Sortieralgorithmen mit Struktogramm
Den Zusatz konnte ich aus Zeitgründen nicht machen.
Alle anderen Vorgaben konnte ich meist recht gut lösen.
Und so sieht die Oberfläche des fertigen Programms aus:
Die einzelnen Funktionen der Elemente sollten mehr oder weniger selbsterklärend sein.
Sortiergeschwindigkeiten:
Das Sortieren des Textes von diesem Blogeintrag ergab folgende Zeiten:
Sortierverfahren: nach Zeichen: nach Wörtern:
Bubble-Sort ca. 79.079 Sekunden ca. 0.170 Sekunden
Ripple-Sort ca. 74.053Sekunden ca. 0.244 Sekunden
Intern-Sort ca. 15.410 Sekunden ca. 0.188 Sekunden
Quick-Sort ca. 0.252 Sekunden ca. 0.013 Sekunden
Quick-Sort - Zeichensortierung (klicken zum Vergrössern) |
|