Hallo!
Kann mir einer einen scnelleres Sortierverfahren als Bubblesort (Laufzeit n*logn) nennen, und mir evtl. den Programmieralgorithmus geben??
Danke im vorraus!
Jenny
Sortieren mit Quicksort:
http://www.goetz-reinecke.de/vb/VBtips/VBtip0188.shtml
greets from michL (vienna)
Danke!
Kannst du mir vielleicht noch etwas über die Laufzeit von Quicksort verraten?
Ciao Jen
Ich persönlich nicht. Auf der HP von dort steht, dass es schneller als BubbleSort ist. (BubbelSort wird dort als erstes Beispiel angeführt, dann kommt das Quicksort)
greets from michL
Kann mir einer einen scnelleres Sortierverfahren als
Bubblesort (Laufzeit n*logn) nennen, und mir evtl. den
Programmieralgorithmus geben??
Bucket Sort hat Laufzeit n, funkt aber nur bei Mengen mit beschränkter Anzahl an verschiedenartigen Elementen.
Wenn du z. B. einen Haufen Buchstaben sortierst, dann machst du für jeden Buchstaben einen Bucket und gehst einfach alle durch und zählst sie. Am Ende erzeugst du eine sortierte Menge die mit der gezählten Anzahl A, dann B usw. beginnt.
Ist wie gesagt schnell, aber nicht so oft anwendbar.
Grüße, Robert
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
Wie von vielen schon erwähnt gibt es den Quicksort.
Der hat eine Laufzeit von n*log(n), wobei n die Anzahl der Elemente ist. Leider kann Quicksort ein Worst-Case haben, d.h. es wird stark gebremst.
Dagegen gibt es den Heapsort. Der hat eine Laufzeit von (n+(n/2))*log(n). Heapsort hat gegenüber Quicksort keinen Worst-Case und wird dadurch immer die gleiche Laufzeit haben (natürliche Schwankungen nicht zu beachten) und Heapsort basiert auf der Baumstruktur (sehr effektiv).
Auf Wunsch kann ich von beiden den Quelltext veröffentlichen.
Gruß Thomas
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
für genaue infos über Laufzeiten schau doch auf einer HP einer UNI nach.
hier ein bsp.
hoffe das hilft
Ich persönlich nicht. Auf der HP von dort steht, dass es
schneller als BubbleSort ist. (BubbelSort wird dort als erstes
Beispiel angeführt, dann kommt das Quicksort)
greets from michL