Neuordnung eines gegebenen Arrays oder einer Liste von Elementen nach einem Vergleichsoperator für die Elemente
Alle Elemente werden entweder in aufsteigender oder in absteigender Reihenfolge neu angeordnet.
Ein stabiler Sortieralgorithmus verändert nicht die ursprüngliche Reihenfolge der 5er-Karten
Beim Selection Sort wird wiederholt das kleinste Element aus dem unsortierten Teil der Liste ausgewählt und in den sortierten Teil der Liste verschoben.
Beispiel: 69, 27, 11, 28, 2
Beim Bubble Sort wird wiederholt das größte Element aus dem unsortierten Teil der Liste in den sortierten Teil der Liste verschoben.
Beispiel: 69, 27, 11, 28, 2
Beim Insertion Sort wird wiederholt das nächste Element aus dem unsortierten Teil der Liste in die richtige Stelle des sortierten Teils der Liste verschoben.
Beispiel: 69, 27, 11, 28, 2
Beim Quick Sort wird wiederholt der Input am freiwählbaren Pivotindex aufgeteilt. Jedes Element wird mit dem Pivotelement verglichen. Ist es kleiner als das Pivotelement wird es in den linken Teil verschoben, ansonsten in den rechten Teil.
Anschließend wird zuerst der linke Teil danach der rechte Teil sortiert.
Beispiel: 10, 80, 30, 90, 40, 50, 70
Beim Merge Sort wird wiederholt der Input in der Mitte aufgeteilt.
Anschließend wird zuerst der linke Teil danach der rechte Teil sortiert.
Anschließend werden der linke und der rechte Teil zusammengeführt.
Beispiel: 69, 27, 11, 28, 2
| Algorithmus | Best | Average | Worst |
|---|---|---|---|
| Selection Sort | O(N²) | O(N²) | O(N²) |
| Bubble Sort | O(N) | O(N²) | O(N²) |
| Insertion Sort | O(N) | O(N²) | O(N²) |
| Quick Sort | O(N log N) | O(N log N) | O(N²) |
| Merge Sort | O(N log N) | O(N log N) | O(N log N) |
Merge Sort hat eine Speicherkomplexität von O(N)