Lineare Strukturen + Sortierung

Sortierverfahren:
Sortierverfahren ordnen Daten eines Arrays oder einer Liste nach bestimmten Kriterien. Folgende Sortierverfahren sind Abiturrelevant.

Selection Sort (Durch Auswählen):
Vergleiche das erste Element mit allen anderen Elementen der Liste.
Finde dabei das kleinste Element und tausche seine Position mit dem ersten Element. Führe diesen Vorgang mit dem nächsten Element fort, bis alle Elemente sortiert sind.
instabil, Laufzeit: O(n²), vergleichsbasiert

Bubble sort (Große Blasen steigen wie im Wasser nach oben):
Vergleiche die Elemente an Position 0 und 1. Wenn das Element an Position 0 größer sein, dann Tausche die Elemente. Verschiebe den Vergleich um ein Element nach rechts. Wiederhohle bis zum Letzten Element. Jede Itteration durch die Liste ist dieses fertig sortiert, und bleibt bei weiteren Itterationen unbeachtet.
stabil, Laufzeit: O(n²), Vergleichsbasiert

Insertion Sort: (Durch einfügen)
Das erste Element gilt als sortiert, die restlichen als unsortiert.
Vergleiche das zweite Element mit dem ersten, sollte dieses kleiner sein, werden die Elemente getauscht. Erweitere den sortierten Bereich um ein Element. Vergleiche nun dass dritte Element mit den zweiten, tausche falls nötig, vergleiche das nun zweite Element mit dem ersten und tausche auch hier falls nötig. Erweitere den sortierten Bereich um Eins und wiederhohle die Schritte biss der unsortierte Bereich leer ist.
stabil, Laufzeit: O(n²), Vergleichsbasiert

Merge Sort: (Durch Teilen + Zusammenfügen)
Die Liste wird rekursiv in zwei Teillisten geteilt, bis jede Teilliste nur noch ein Element enthält.
Der Algorithmus durchläuft iterativ jeweils zwei benachbarte Teillisten und vergleicht in jedem Schritt die jeweils ersten Elemente. Das kleinere Element wird in eine neue Endliste eingefügt. In der nächsten Iteration wird mit dem zweiten Element der bisher kleineren Liste weitergemacht. Dieser Vorgang wiederholt sich, bis durch beide Listen durchiteriert wurde.
Die Endliste wird so lange mit weiteren Listen mit derselben Länge verbunden, bis nur noch eine, nun sortierte Liste vorliegt.
stabil, Laufzeit: O(n log n), Vergleichsbasiert