Insertionsort

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 ${\mathcal {O}}(n^{2})$.

Weblinks

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

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort