Quicksort
Quicksort (von engl. quick – schnell, to sort – sortieren) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet. Er wurde 1962 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack).
Shellsort
Shellsort ist ein von Donald L. Shell im Jahre 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert.
Selectionsort
Der Begriff Sortierlese oder Selection-Sort (englisch selection »Auswahl«, to sort »sortieren«), auch MinSort (von Minimum) bzw. MaxSort (von Maximum) oder Selectsort genannt, bezeichnet einen naiven Sortieralgorithmus, der in-place arbeitet und sich stabil implementieren lässt. Die Komplexität von SelectionSort ist, in der Landau-Notation ausgedrückt, O(n2).
Quellen
Die Algorithmen sowie die kurzen Einleitungstexte zu den jeweiligen Sortierverfahren entstammen der deutschsprachigen Wikipedia:
- Quicksort [wikipedia.de]
- Shellsort [wikipedia.de]
- Selectionsort [wikipedia.de]
Die für die Sortierdemos verwendeten Icons wurden aus dem Crystal Clear [kde-look.org] Theme für KDE entnommen und nachträglich bearbeitet um ins Farbschema zu passen. Zur Manipulation der DOM wurde weitgehend auf die jQuery JavasScript Bibilothek zurückgegriffen.