Sortieralgorithmen
Quicksort
Der Quicksort-Algortithmus ist eines der schnellsten und zugleich einfachsten Sortierverfahren. Es arbeitet nach dem Divide-and-Conquer-Prinzip.
Es wird zunächst ein Pivotelement ausgewählt und die Liste in zwei geteilt. Die Elemente, die kleiner als das Pivotelement sind, kommen in die erste Liste und die anderen in die zweite. Mit den entstehenden Listen wird genauso fortgefahren, bis es nur noch Teillisten der Länge 1 gibt. Diese Listen werden nun der Reihe nach wieder zusammengefügt.
Mergesort
Ähnlich wie bei Quicksort beruht das Verfahren auf der Divide-and-Conquer-Strategie. Die zu sortierende Folge wird in zwei gleichgroße Hälften geteilt. Die entstehenden Listen werden weiter und weiter geteilt, bis es wieder nur noch Teillisten der Länge 1 gibt. Zusammengefügt wird, indem die ersten beiden Elemente zweier Teillisten verglichen werden, das kleinere gelöscht und in eine neue Liste eingetragen wird. Die neuen ersten beiden Elemente verglichen, das kleinere gelöscht und in die neue Liste eingetragen wird...
Bubblesort
Bubblesort ist einer der simpelsten Sortieralgorithmen.
Im ersten Durchlauf wird nach dem kleinsten Element gesucht, im zweiten Durchlauf nach dem zweitkleinsten usw.
Man geht den Array immer von hinten nach vorne durch. Zunächst vergleicht man das letzte mit dem vorletzten Element. Ist das hintere kleiner, werden die beiden Elemente vertauscht. Dann wird mit dem vorletzten und dem vorvorletzten weitergemacht. Dadurch bleiben die größeren liegen und die kleineren Elemente werden nach vorne durchgereicht.
Insertionsort
Man hat eine zu sortierende Folge a0, a1, ... , an-1, wobei der erste Teil a0, a1, ... , ak-1 bereits aufsteigend sortiert ist und der zweite Teil ak, ak+1, ... , an-1 noch unsortiert ist. Zu Anfang besteht der sortierte Teil nur aus a0, zum Schluss aus allen Elementen a0, a1, ... , an-1.
Das Element ak wird als nächstes in die bereits sortierte Liste eingefügt, indem es der Reihe nach mit ak-1, ak-2 usw. verglichen wird. Sobald ein Element aj mit aj≤ak gefunden wird, wird es hinter dieses eingefügt. Wird kein solches Element gefunden, wird ak an den Anfang der Folge gesetzt.
Damit ist der sortierte Teil um ein Element länger geworden. Im nächsten Schritt wird ak+1 in den sortierten Teil eingefügt...
Vergleich Mergesort und Quicksort
von http://www.gm.fh-koeln.de/~ehses/ap/folien/folien9.pdf
- Mergesort ist garantiert O(n log n), Quicksort im Mittel
- Die Anzahl der Vergleich und der Datenbewegungen ist bei Mergesort n log2(n)
- Quicksort hat im Mittel O(1.4 n log2 n) Vergleiche
- Quicksort hat im Mittel O(0.7 n log2 n) Datenbewegungen
- Quicksort ist schneller, wenn die Vergleiche schneller sind als die Datenbewegungen (einfache Datentypen)
- Mergesort ist schneller, wenn die Vergleiche die Zeit dominieren (Objekte)
- Es gibt Varianten von Mergesort für Felder und Listen (nicht rekursiv)
Links
zu Laufzeiten s.a.: O-Notation
www.sortieralgorithmen.de - mit klasse Applet
Merkblatt zu topologisches Sortieren von Augustin