Auf dieser Seite werden die folgenden Sortieralgorithmen behandelt:
- Bubble Sort
- Sortieren durch Austauschen
- Selection Sort
- Sortieren durch Auswählen
- Insertion Sort
- Sortieren durch Einfügen
- Quick Sort
- Rekursives Sortieren gemäss "divide and conquer"
- Heap Sort
- Sortieren mit einem Heap
Die ersten drei Verfahren sind von der Technik her relativ einfach. Die Performance ist allerdings auch nicht besonders gut. So haben denn auch alle Verfahren im schlimmsten Fall (worst case) quadratische Laufzeit (in Abhängigkeit von der Arraygrösse).
Quick Sort ist der wohl bekannteste Sortieralgorithmus. Er wird meist rekursiv implementiert, da er nach dem "divide and conquer"-Prinzip funktioniert. Dabei wird der Array in zwei Patitionen aufgeteilt (divide), die dann rekursiv weiter sortiert werden. Die durchschnittliche Laufzeit von Quick Sort ist O(n log(n)). Im worst case kann der Algorithmus aber auch quadratisch werden.
Heap Sort ist ein sehr effizientes Verfahren, das auch im worst case die bestmögliche Laufzeit von O(n log(n)) erreicht. In der Praxis ist allerdings Quick Sort oft schneller.
Java Applikation
Das folgende Java Programm zeigt anhand einer Graphik die Funktionsweise der fünf oben beschriebenen Sortieralgorithmen.
SortingToolbox.jar (executable jar file)
Ergänzendes Material
- SortingToolbox.zip
- Java Applikation (executable jar file, gezippt)
- SortingToolbox_doc.zip
- Dokumentation (Online-Version)
Hinweis: Laden Sie das ZIP-Archiv herunter und entpacken Sie die Dateien.