====== Selectionsort ======

==== Prinzip ====

Sei S der sortierte Teil des Arrays und U der unsortierte Teil. Am Anfang ist S noch leer, U entspricht dem ganzen Array. Das Sortieren durch Auswählen funktioniert so:

Suche das kleinste Element in U und vertausche es mit dem ersten Element.

Danach ist das Array bis zu dieser Position sortiert. Das kleinste Element wird in S verschoben. S ist um ein Element gewachsen, U um ein Element kürzer geworden. Anschließend wird das Verfahren solange wiederholt, bis das gesamte Array abgearbeitet worden ist.

Alternativ sucht man das Maximum, also das Element mit dem größten Sortierschlüssel. Das Maximum wird dann mit dem letzten Element des Arrays vertauscht und man erhält ebenfalls ein sortiertes Teilarray der Länge 1, allerdings rechts, und ein unsortiertes Array der Länge n-1, diesmal links. Der Algorithmus wird dann auch auf das unsortierte Teilarray angewendet.

Zudem existieren auch Ansätze, in denen beide Varianten (MinSort und MaxSort) gemeinsam arbeiten, sprich während eines Durchlaufes das größte und das kleinste Element eines Arrays gesucht und dieses dann jeweils an den Anfang, bzw. an das Ende des Arrays, gesetzt werden. Dadurch hat man in der Regel eine Beschleunigung um den Faktor 2.