Selection sort
Selection sort sorteert een lijst zoals veel mensen de kaarten in hun hand sorteren: zoek de kleinste, leg die vooraan, en zoek dan de kleinste van de rest. Het doet veel vergelijkingen maar heel weinig verwisselingen, en de looptijd hangt nauwelijks af van de volgorde van de lijst.
Het idee
Verdeel de lijst in een gesorteerd deel links, eerst leeg, en een ongesorteerd deel rechts. Doorzoek het ongesorteerde deel en onthoud waar de kleinste waarde staat. Verwissel die waarde met de eerste ongesorteerde waarde: het gesorteerde deel is één groter geworden. Herhaal dit tot er één waarde over is, en dat moet de grootste zijn.
Een voorbeeld
Neem 5, 1, 4, 2, 8. De eerste ronde bekijkt alle vijf waarden, vindt 1 als kleinste en verwisselt die met 5: 1, 5, 4, 2, 8. De tweede ronde bekijkt 5, 4, 2, 8, vindt 2 en verwisselt die met 5: 1, 2, 4, 5, 8. De derde ronde vindt 4 al op zijn plek, en de vierde vindt 5 al op zijn plek, dus er verschuift niets. Dat zijn 4 + 3 + 2 + 1 = 10 vergelijkingen en maar 2 verwisselingen. Bubblesort heeft voor dezelfde lijst 4 verwisselingen nodig.
Altijd evenveel vergelijkingen
Om zeker te weten welke waarde de kleinste is, moet het zoeken elke overgebleven waarde bekijken. Ronde 1 doet n − 1 vergelijkingen, ronde 2 doet er n − 2, en zo verder tot 1, samen n(n − 1)/2. Dat aantal hangt niet af van de lijst: een gesorteerde lijst kost precies evenveel vergelijkingen als een omgekeerde. Selection sort kan niet vroeg stoppen, want een ronde die de kleinste waarde al vooraan vindt, weet daarmee nog niets over de rest.
Weinig verwisselingen
Elke ronde doet hoogstens één verwisseling, dus selection sort doet nooit meer dan n − 1 verwisselingen, en slaat de verwisseling over als de kleinste waarde al op zijn plek staat. Bubblesort en insertion sort doen evenveel verwisselingen als er paren in de verkeerde volgorde staan, en dat kunnen er ongeveer n²/2 zijn. Als een waarde schrijven veel duurder is dan twee lezen, bijvoorbeeld bij geheugen dat bij elke schrijfactie slijt, is het kleine aantal verwisselingen een voordeel.
Niet stabiel
Een sorteermethode is stabiel als gelijke waarden hun oorspronkelijke volgorde houden. Selection sort is dat niet, omdat een verwisseling over een grote afstand een waarde voorbij een gelijke waarde kan brengen. In 2, 2, 1 verwisselt de eerste ronde de eerste 2 met de 1, wat 1, 2, 2 geeft met de twee 2'en nu in omgekeerde volgorde. Een versie die de tussenliggende waarden opschuift in plaats van te verwisselen is stabiel, maar verplaatst veel meer waarden.
Probeer het zelf
Open de app en druk op Afspelen, of druk op Stap om per vergelijking te gaan. De waarde die bekeken wordt is gemarkeerd, de kleinste waarde tot nu toe heeft een eigen kleur, en elke ronde eindigt met een verwisseling naar het gesorteerde deel links. Probeer een gesorteerde en een omgekeerde lijst: de vergelijkingen komen gelijk uit, alleen de verwisselingen verschillen.
Veelgestelde vragen
Wat is de tijdcomplexiteit van selection sort?
O(n²) in elk geval: precies n(n − 1)/2 vergelijkingen voor n waarden, in welke volgorde ook. Het doet hoogstens n − 1 verwisselingen en heeft maar O(1) extra geheugen nodig.
Wat is het verschil tussen selection sort en bubblesort?
Bubblesort verwisselt buren onderweg en kan vroeg stoppen zodra een ronde niets verwisselt. Selection sort onthoudt alleen waar de kleinste waarde staat en doet één verwisseling aan het eind van elke ronde. Selection sort doet minder verwisselingen; bubblesort is sneller bij lijsten die bijna gesorteerd zijn.
Is selection sort stabiel?
Nee. Een verwisseling kan een waarde voorbij een gelijke waarde verplaatsen, zodat gelijke waarden van volgorde kunnen wisselen. Het kan stabiel worden gemaakt door waarden op te schuiven in plaats van te verwisselen, wat meer verplaatsingen kost.
Wat heeft heapsort met selection sort te maken?
Heapsort is een selection sort met een snellere manier om de volgende waarde te vinden: het houdt het ongesorteerde deel in een heap, zodat elke keuze ongeveer log n stappen kost in plaats van een volledige doorzoeking. Daarmee daalt het totaal tot O(n log n).
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer selection sort