Was ist besser: Selection Sort, Bubble Sort oder Quick Sort und warum?
6 Antworten
Quick Sort ist im normalen Fall das beste, im Extremfall kann es aber sein dass wegen Speichermangel das Programm "abstürzt".
Bubble Sort ist zum schnellen Programmieren mit 2 For Schleifen leichter auswendig zu lernen und mit weniger Fehler. Wenn es um weniger als 100 zu sortierende dinge geht, dann bubble sort (mit den schnellen computern heutzutage kann man locker auch bis 1000 dinge gehen).
Selection Sort ist ein Kompromiss aus dem ersten und dem zweiten.
Speichermangel beim Quick-Sort kann einfach auch so aussehen, dass die maximalen Rekursionsebenen die der Compiler erlaubt und Stack-Speicher reserviert überschritten ist.
Ein Bubble-Sort ist einfach zu schreiben und dann gut, wenn man keinen fertigen Sort zut Verfügung hat. Dafür ist er langsam, für einfache Anwendung u.U. trotzdem sinnvoll sein. Für einen integrierten Sort z.B. in einem Compiler muss man etwas universelles anbieten, da man nicht weiß, was die künftigen Programmierer damit sortieren werden. Im allgemeinen verwendet man fertige Sortprogramme, wo man nicht weiß, nach welchem Verfahren diese sortieren. Im Prinzip interessiert das auch niemanden.
Ganz klar quicksort. Komplexitätsklasse ist O(n * log(n)). Wäre bei den anderen beiden n Quadrat...
(n = Menge der zu sortierenden Elemente)
Allerdings ist Quicksort nicht stabil und braucht zusätzlichen Speicher...
Schau mal hier.
Da sind alle Sortierverfahren aufgelistet, mit Laufzeitverhalten, Stabilität und Speicherplatz...
Welcher Algorithmus der Beste ist hängt von deinen Kriterien ab...
Quick-Sort ist in dieser Gruppe der Champion.
Warum das so ist: Siehe die Komplexität. Dort liegt Quicksort in aller Regel vorn.
Warum sollte es? Es gibt verschiedene Implementierungen des Quicksort - So kann ich z.B. den 'Stack' auf den Heap knallen.
Unabhängig davon ist der Stackframe im Verhältnis klein zur zu sortierenden Datenmenge. So schnell ist der nicht voll.
D.h.:
Zur Erinnerung: Die Komplexität des Stacks liegt bei log_2(n), wenn mein Stack also 100 000 Frames aufnehmen kann, kann ich Problemgrößen in der Größenordnung 2^100 000 noch ohne feuchte Augen erledigen.
Reicht das nicht kann ich immernoch den Stack vergrößern oder, wie bereits geschrieben, selbst implementieren.
Mein Problem ist in der Regel eher der begrenzte Hauptspeicher, aber dafür gibt es dann immernoch andere Verfahren.
Was hat denn der Algorithmus mit der Unfähigkeit eines Programmierers zu tun? Weil Quicksort komplexer ist?
Es gibt signifikant bessere vergleichbasierte Sortieralgorithmen, die das allgemeine Sortierproblem lösen?
Na, dann nenne doch Ross und Reiter, denn mich würde durchaus interessieren, wo sich die mathematischen Beweise zu dem Thema geirrt haben.
Varianten von Quicksort bzw. eine Klasse von Sortieralgorithmen, von denen Quicksort nur eine ist: https://en.wikipedia.org/wiki/Quicksort letzter Abschnitt
Naja, Varianten sind eben nur das, Varianten.
Einige der Varianten sind gar nicht in der Lage das allgemeine Sortierproblem zu lösen und daß es für spezielle Probleme respektive Gesamtsituationen bessere Optionen gibt, wurde ja nicht bestritten.
Beispiel: Three-way radix quicksort, hier wird von einer speziellen Ordnungsrelation ausgegangen.
was nutzt einem das aber wenn irgendwann nach nem jahr sich das programm aus zufälligen gründen mit "stack overflow" verabschiedet und die ganze arbeit verloren geht die man gemacht hat.