Selectionsort

Selectionsort ist ein Sortieralgorithmus und arbeitet wie folgt:

Gegeben: Eine Liste A der Länge n:

• Unterteile die Liste in einen sortierten und einen unsortierten Bereich.
• Der sortierte Bereich ist zu Beginn leer, der unsortierte Bereich enthält die ganze Liste
• Wiederhole n Mal:
  • Gehe durch den gesamten unsortierten Bereich durch und finde das kleinste Element
  • Füge dieses Element am Ende des sortierten Bereichs ein

Laufzeit

Die Liste mit $n$ Elementen muss $n$ Mal durchlaufen werden, wobei beim ersten Durchgang $n$ Elemente betrachtet werden, beim zweiten Durchgang $n-1$ Elemente, beim dritten Durchgang $n-2$ Elemente und so weiter, bis beim letzten Durchgang nur noch ein Element betrachtet wird. Insgesamt werden also $1+2+3+\cdots +n=\frac{n^2+n}{2}$ Elemente betrachtet. Damit liegt die Laufzeit in ${𝒪}(n^2)$.

Weblinks

• Sortieralgorithmen auf VisuAlgo.net 🇬🇧 🇨🇳 🇮🇩
• Selectionsort getanzt 🇬🇧

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort