Sortieralgorithmen
Wir unterscheiden einfache Sortierverfahren und Divide-and-Conquer-Methoden.
Einfache Sortierverfahren
Die Sortierung erfolgt von links nach rechts. Dabei wird jedes neue Element mit den bereits sortierten Elementen verglichen und an die richtige Stelle eingefügt.
Die Sortierung erfolgt von links nach rechts. Dabei wird jedes neue Element einsortiert, in dem es mit dem kleinsten unsortierten Element vertauscht wird.
Die Sortierung erfolgt von links nach rechts. In jedem Schritt wird das aktuelle Element mit dem rechten Nachbarelement verglichen und gegebenfalls vertauscht. Dieser Ablauf wird solange wiederholt, bis die Liste vollständig sortiert ist. Bei jedem neuen Durchlauf muss dabei das letzte Element des vorherigen Durchlaufs nicht mehr verglichen werden, da es bereits das größte Element der restlichen Elemente ist.
Divide-and-Conquer-Methoden
Bei diesen Methoden werden die zu sortierenden Elemente rekursiv in kleinere Teilmengen aufgeteilt und sortiert. Anschließend werden die Teilmengen zu einer sortierten Gesamtmenge zusammengefügt.
Vertreter dieser Kategorie sind die Algorithmen Quicksort and Mergesort.