Re: Sortiervervahren

Hallo!

Bubblesort ist das wird zwar immer gern als Programmierbeispiel genommen, ist aber bzgl. Performance der schlechteste Sortieralgorithmus den ich kenne (keine Ironie, Tatsache).

Für das Sortieren von Daten im Speicher hat sich Quicksort als der Standard-Wald-und-Wiesen-Algorithmus etabliert (schnell, einfach zu implementieren). Quicksort hat die Komplexität n log n, im ungünstigsten Fall n² (wenn alle Elemente umgekehrt sortiert vorliegen). Es ist in der Praxis jedoch nicht allein die theoretische Komplexität relevant, sondern auch die Kosten der tatsächlich duchgeführten Operationen.

Die meisten Programmiersprachen bieten Quicksort als run time library Routine an, wobei die typischen Implementierungen (z.B. für C/C++-Compiler) optimiert (Assembler) und mit allen algorithmischen Tricks (Median of three, etc.) ausgestattet sind. Diese Bibliotheks-Routinen kann man sorglos verwenden.

Mein Wissensstand: Ich glaube, es gibt einige Spezialalgorithmen, die eine geringere Komplexität als n log n (in der Theorie) haben, jedoch bis auf Spezialsituationen keine Praxisrelevanz haben. Dem gegenüber wird an Quicksort noch immer 'rumgebastelt und optimiert (da gibt's einige Promotionen über dieses Thema), um noch das letzte herauszuholen. (Wenn hier jemand genauer bescheid weis, bitte sagen!)

Eine gute, verständliche aber doch ausführliche Einführung in Sortieralgorithmen ist zu finden in:

"Algoritmen in C", Robert Sedgewick, Addison-Wesley
(für andere Programmiersprachen gibt es auch andere Ausgaben)

Mein kurze Suche im Web hat folgende Site ergeben:
http://www.dseifert.de/de/studium/referate/sortier.html

Einfach mal selbst auf die Suche machen, Stichwort: Sortieralorithmen...

Viel Spaß,
Bernhard