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 ]

(c) 2004 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License