Selection sort is een eenvoudig sorteeralgoritme dat de lijst verdeelt in een gesorteerd deel en een ongesorteerd deel. Het werkt door herhaaldelijk het kleinste (of grootste, afhankelijk van de sorteervolgorde) element te vinden van het ongesorteerde deel en dit te plaatsen aan het begin van het gesorteerde deel. Via deze link krijg je een visuele voorstelling van het selection sort algoritme.

Hier is een basisstappenplan voor Selection sort:

1. Begin met het volledige ongesorteerde deel van de lijst.
2. Zoek het kleinste (of grootste) element in het ongesorteerde deel.
3. Wissel dit element met het eerste element van de ongesorteerde lijst.
4. Nu is het eerste element van de lijst gesorteerd.
5. Herhaal dit proces voor de rest van de lijst door het ongesorteerde deel steeds te verkleinen.
6. Na elke iteratie van dit proces wordt het gesorteerde deel van de lijst vergroot en het ongesorteerde deel verkleind, totdat de hele lijst gesorteerd is.

Hoewel Selection sort eenvoudig te begrijpen en te implementeren is, heeft het een inefficiënte tijdscomplexiteit van O(n^2) in alle gevallen, wat betekent dat het niet efficiënt is voor grote lijsten. Het is echter handig voor kleine lijsten of als een educatief hulpmiddel vanwege zijn eenvoud en duidelijkheid.

Schrijf een functie selectionsort met een lijst van getallen als parameter die een gesorteerde lijst als returnwaarde heeft.

>>> selectionsort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]
>>> selectionsort([73, 41, 74, 72, 8, 10, 57, 84, 68, 21])
[8, 10, 21, 41, 57, 68, 72, 73, 74, 84]