Was sind Sorting Algorithms?

Wir verwenden Sortierungs-Algorithmen, um Elemente in einer Liste in eine Reihenfolge zu sortieren. Neben anderen Anwendungen kann die Sortierung angewendet werden, um einen Datensatz für einen anderen Algorithmus vorzubereiten, zum Beispiel für die Binäre Suche.

Comparision Sort

Bubble Sort (Best: O(n) , Worst: O(n^2))



Bubble Sort beginnt am Anfang der Liste und vergleicht jedes Paar benachbarter Elemente. Wenn das Erste größer als das Zweite ist, werden sie vertauscht. Dann beginnt es wieder am Anfang der Liste und wiederholt diesen Vorgang, bis zum Ende der Liste. Da seine Zeitkomplexität im Durchschnitt und im schlimmsten Fall Ο(n^2) beträgt, eignet sich dieser Algorithmus eher für kleine oder nahezu geordnete Datensätze.

Selection Sort (Best: O(n) , Worst: O(n^2))



Die Liste wird bei diesem Algorithmus in einen sortierten Teil -links- und einen unsortierten -rechts- geteilt. Anfänglich gibt es eine sortierte Unterliste (anfangs leer) und die unsortierte Hauptliste. Dann sucht der Algorithmus nach dem kleinsten Element in der unsortierten Liste und tauscht es mit dem ganz linken unsortierten Element aus, wobei die Unterlistengrenzen um ein Element nach rechts verschoben werden. Wie Bubble Sort hat dieser Algorithmus eine quadratische Zeitkomplexität Ο(n^2), ist also auch eher für kleine oder nahezu geordnete Datensätze geeignet. Allerdings führt Selection Sort weniger Swaps durch als Bubble Sort.

Insertion Sort (Best: O(n^2) , Worst: O(n^2))



Insertion Sort hält eine sortierte Unterliste am Anfang der Liste und sucht für jedes Element aus der Liste nach der richtigen Position in dieser Unterliste, um dieses Element einzufügen. Insertion Sort hat auch eine quadratische Zeitkomplexität für durchschnittliche und schlechte Fälle, ist jedoch der schnellste Sortieralgorithmus für kleine Listen.

Merge Sort ( O(n log n) , SPACE: O(n log n))



Merge-Sort ist ein Sortieralgorithmus, der eine Divide- & Conquer-Technik verwendet, um eine gegebene Liste zu sortieren, was bedeutet, dass ein Problem in kleinere Teile zerlegt wird, um es einfacher zu lösen. Merge Sort beginnt mit dem Aufteilen der Liste in Hälften und fährt fort, diese Unterlisten aufzuteilen, bis nur noch Unterlisten mit einem einzigen Element übrig sind. Dann werden die Unterlisten zu sortierten Unterlisten zusammengefügt unzwar solange, bis eine einzige sortierte Liste entsteht.

Merge Sort wird in Bezug auf die Zeitkomplexität in O(n log n) ausgeführt, seine Raumkomplexität beträgt O(n), da sie Hilfsarrays verwendet, um die Unterlisten zu speichern. Außerdem können wir Multithreading nutzen, um Merge Sort zu implementieren, indem wir beispielsweise jede Hälfte in getrennte Threads sortieren. Darüber hinaus können wir Merge Sort mit anderen Sortieralgorithmen kombinieren, zum Beispiel könnten wir, anstatt die Liste in Einzelelement-Unterlisten aufzuteilen, sie in kleine Unterlisten mit wenigen Elementen aufteilen und diese mit Insertion Sort sortieren.

Quick Sort
(Best: O(n log n), Worst: O (n^2) , SPACE: Best: O( log n), Worst: O(n))



Quick Sort ist ein In-Place-Sortieralgorithmus, der eine Divide- &Conquer-Technik verwendet. Quick Sort beginnt mit der Auswahl eines Elements aus der Liste als Pivot-Element, normalerweise ist es das erste oder letzte Element. Als Nächstes ordnen wir die anderen Elemente neu an, sodass alle Elemente, die kleiner als der Pivot sind, nach links und alle Elemente, die größer als der Pivot sind, nach rechts gehen. Der wichtige Teil von Quick Sort ist die Wahl des Pivots, da eine schlechte Wahl zu einer ungünstigsten Zeitkomplexität führt, wobei die durchschnittliche Fallzeitkomplexität dieses Algorithmus O(n log n) beträgt, während im schlechtesten Fall case ist O(n²). Jedoch kann der schlimmste Fall mit einer randomisierten Version dieses Algorithmus vermieden werden. Außerdem ist Quick Sort im Gegensatz zu Merge Sort ein In-Place-Algorithmus, der den Vorteil einer konstanten Raumkomplexität O(1) hat.


Non-Comparision Sort

Counting Sort ( O(n + k) , SPACE: O(k))
Die Zählsortierung ist ein Algorithmus, mit dem wir in bestimmten Fällen ein Array in linearer Zeit sortieren können. Um die Zählsortierung zu verwenden, darf unser Array nur Dezimalzahlen enthalten. Es wird davon ausgegangen, dass wir die Min- und Max-Werte kennen. Counting Sort funktioniert, indem die Anzahl der Objekte gezählt werden. Jeder der unterschiedlichen Schlüsselwerte wird anhand dieser Zählungen arithmetisch verwendet, um die Positionen jedes Schlüsselwerts in der Ausgabesequenz zu bestimmen.

Die Laufzeit des Algorithmus ist linear in der Anzahl der Elemente und der Differenz zwischen den maximalen und minimalen Schlüsselwerten. Deshalb ist der Algorithmus nur für den direkten Einsatz in Situationen geeignet, in denen die Variation der Schlüssel nicht wesentlich größer ist als die Anzahl der Elemente. Er wird jedoch oft als Unterprogramm in einem anderen Sortieralgorithmus (Radixsort), verwendet, der größere Schlüssel effizienter handhaben kann. Die Zählsortierung funktioniert am besten, wenn der Zahlenbereich für jedes Arrayelement sehr klein ist.

Bucket Sort (O(n + k))
Bucket Sort kann für viele der gleichen Aufgaben wie Counting Sort verwendet werden, mit einer ähnlichen Zeitanalyse. Im Vergleich zur Counting Sort erfordert die Bucket-Sortierung jedoch verknüpfte Listen, dynamische Arrays oder eine große Menge an vorab zugewiesenem Speicher, um die Sätze von Elementen in jedem Bucket zu speichern. Counting Sort speichert stattdessen eine einzelne Zahl (die Anzahl der Elemente) pro Bucket.

Radix Sort (Best: O(n) , Worst: O(n^2)
In der Informatik ist Radixsort ein nicht vergleichender Dezimalzahl-Sortieralgorithmus, der Daten mit ganzzahligen Schlüsseln sortiert. Dies geschieht indem Schlüssel nach den einzelnen Ziffern gruppiert werden, die dieselbe signifikante Position und denselben Wert haben. Eine Positionsnotation ist erforderlich, aber da ganze Zahlen Zeichenfolgen (z. B. Namen oder Datumsangaben) und speziell formatierte Gleitkommazahlen darstellen können, ist die Radixsortierung nicht auf ganze Zahlen beschränkt.