Sortieralgorithmen

Der grundlegendste Sortieralgorithmus, der wiederholt benachbarte Elemente vergleicht und sie austauscht, wenn sie in falscher Reihenfolge sind. Wie Blasen, die an die Oberflache steigen, bewegen sich grossere Werte allmahlich zum Ende des Arrays. Am besten geeignet fur kleine Datensatze oder Bildungszwecke, um Sortiergrundlagen zu verstehen.

Findet wiederholt das kleinste Element und verschiebt es nach vorne. Jede Iteration 'wahlt' das Minimum aus den verbleibenden Elementen und platziert es nach dem sortierten Teil. Einfach zu implementieren mit minimalem Speicherverbrauch, benotigt aber immer O(n^2) Zeit unabhangig von der Eingabe.

Ein hocheffizienter Sortieralgorithmus, der ein Pivot-Element auswahlt und das Array mit kleineren Werten links und grosseren rechts partitioniert. Durchschnittlich O(n log n) und die am weitesten verbreitete Sortiermethode in der Praxis. Bildet die Grundlage der eingebauten Sortierfunktionen in den meisten Programmiersprachen.

Verwendet eine binare Heap-Datenstruktur, indem zuerst ein Max-Heap aufgebaut wird und dann wiederholt das Wurzelelement extrahiert wird, um zu sortieren. Garantiert O(n log n) Zeitkomplexitat in allen Fallen ohne zusatzlichen Speicher. Dient auch als Grundlage fur Priority-Queue-Implementierungen.

Ein nicht-vergleichsbasierter Sortieralgorithmus, der Vorkommen jedes Elements zahlt und Arithmetik verwendet, um Positionen zu bestimmen. Erreicht O(n+k) Zeitkomplexitat, wobei k der Bereich der Eingabewerte ist. Ideal zum Sortieren von ganzen Zahlen innerhalb eines bekannten, begrenzten Bereichs. Bildet die Grundlage fur Radix Sort.

Ein nicht-vergleichsbasierter Sortieralgorithmus, der Elemente Ziffer fur Ziffer von der niedrigstwertigen zur hochstwertigen verarbeitet. Verwendet Counting Sort als Unterroutine fur jede Ziffernposition. Erreicht O(d(n+k)) Zeit, wobei d die Anzahl der Ziffern ist. Hervorragend zum Sortieren von ganzen Zahlen oder Strings fester Lange.

Eine Optimierung von Insertion Sort, die den Austausch von weit entfernten Elementen erlaubt. Verwendet eine Luckensequenz, die auf 1 abnimmt, wodurch der Algorithmus Elemente schneller naher an ihre endgultigen Positionen bewegen kann. Benannt nach Donald Shell, der ihn 1959 erfand.

Ein verteilungsbasierter Sortieralgorithmus, der Elemente in eine Anzahl von Eimern verteilt. Jeder Eimer wird dann einzeln mit einem anderen Sortieralgorithmus sortiert. Funktioniert am besten, wenn die Eingabe gleichmassig uber einen Bereich verteilt ist. Durchschnittliche Zeitkomplexitat ist O(n+k).

Ein Divide-and-Conquer-Algorithmus, der das Array halbiert, jede Halfte rekursiv sortiert und sie dann wieder zusammenfuhrt. Garantiert O(n log n) Zeit und ist stabil, benotigt aber zusatzlichen Speicher. Besonders effektiv fur grosse Datensatze und verkettete Listen-Sortierung.

Funktioniert wie das Sortieren von Spielkarten in der Hand - jedes Element wird nacheinander an die richtige Position eingefugt. Lauft in O(n) Zeit fur bereits sortierte Daten, was ihn hocheffizient fur kleine Arrays oder fast sortierte Datensatze macht. Einfacher, aber adaptiver Algorithmus.

Verbesserung gegenuber Bubble Sort, die kleine Werte am Ende der Liste (Schildkroten) eliminiert. Verwendet eine schrumpfende Luckensequenz, die mit der Arraylange beginnt und die Worst-Case-Komplexitat verbessert. Praktisch fur mittelgrosse Datensatze, bei denen einfache Implementierung uber optimale Leistung geschatzt wird.

Einfacher Sortieralgorithmus ahnlich Insertion Sort, benannt nach der Art, wie Gartenzwerge Blumentopfe sortieren. Bewegt sich ruckwarts, wenn Elemente nicht in Ordnung sind, dann wieder vorwarts. Obwohl O(n^2) wie Bubble Sort, macht seine Einfachheit ihn nutzlich fur das Lehren von Sortierkonzepten und die Handhabung kleiner Datensatze.