6. Schlussbemerkungen
[ Zurück zum Inhaltsverzeichnis ]
6.1 Fazit
Es zeigt sich, dass die Wahl eines geeigneten Sortieralgorithmus' durchaus keine einfache Entscheidung
ist. Quicksort z.B. ist das schnellste der Verfahren, welche sich auf Schlüsselvergleiche stützen, hat
aber eine worst-case-Laufzeit von O(n2). Mergesort wiederhin ist nicht sehr schnell und
benötigt proportional zu n zusätzlich viel Speicher, dafür hat es eine worst-case-Komplexität von
O(n*log(n)), ist leicht zu implementieren, kaum störanfällig und vor allem bei Problemen zu verwenden,
bei denen immer wieder Datensätze in einen bestehenden sortierten Datenbestand integriert werden sollen.
Heapsort wiederhin vereint die Laufzeitkomplexität von O(n*log(n)) im schlechtesten Fall von
Mergesort mit dem Quicksort-Vorteil, dass kein zusätzlicher Speicher benötigt wird - dafür ist es aber
sehr langsam in der Ausführung.
Als echte Alternative kann man die digitalen Sortierverfahren ansehen. Schon Radix Exchange Sort ist bei
zufälligen Permutationen Quicksort fast gleichwertig, doch erst das optimierte lineare Straight Radix Sort
verspricht spürbare Geschwindigkeitvorteile von 30-50%. Zusätzlicher Speicherbedarf in Höhe der
Eingabedaten ist der Tribut, den man dafür zahlen muss, daher ist es auch kein Universalmittel und sollte
nur dort ohne Bedenken eingesetzt werden, wo sicher ist, dass genügend Speicher zur Verfügung steht und wo
Geschwindigkeit alles entscheidend ist. Auf allen anderen Systemen ist ein verbessertes Quicksort zu
empfehlen, welches auch schnell arbeitet und exzellent problemabhängig angepasst werden kann.
Die endgültige Wahl und Implementation eines der vorgestellen Algorithmen sollte am Ende allerdings
vor allem bei ernsthaften Produktivsystemen einem Experten überlassen werden, um der Gefahr einer
gefährlichen Fehlentscheidung vorzubeugen.
Nachfolgend soll noch ein Diagramm angegeben werden, in welchem ich die empirische Messung der Laufzeiten
von den einzelnen Sortierverfahren fest gehalten habe und welches die Entscheidungsfindung nach dem
optimalen Sortieralgorithmus vereinfachen soll:
6.2 Quellennachweis/Buchempfehlungen
Die hier dargestellten Informationen habe ich vor allem drei Büchern entnommen, die ich hier auch
weiter empfehlen möchte. Aus dem ersten entstammen zudem die meisten Quelltexte, wobei hier und da
sinnvolle bzw. notwendige Änderungen durchgeführt wurden.
6.3 Downloads
PDF: Zeitoptimale Sortierverfahren (ACHTUNG: teilweise falsch formatiert)
ZIPPED HTML: Zeitoptimale Sortierverfahren (empfohlen)
Testprogramm zeitoptimaler Verfahren: zeitopt_sort.c
Testprogramm elementarer Verfahren: elem_sort.c
6.4 Kontakt
Matthias Jauernig (aka RTC, author/maintainer):
Mail: [email protected], ICQ UIN: 81028529
Tobias Hammerschmidt (aka i84cOre, writer):
Mail: [email protected], ICQ UIN: 148859859
[ Zurück zum Inhaltsverzeichnis ]