- Vergeleken
- Kleinste tot nu toe
- Verwisseld
- Op zijn plek
Selection sort
Selection sort bouwt de gesorteerde lijst van voren op. Elke ronde doorzoekt de waarden die nog niet gesorteerd zijn, onthoudt de kleinste en verwisselt die naar de eerste ongesorteerde plek. Speel het sorteren af op elke snelheid, of ga er per vergelijking doorheen, en volg de tellers voor vergelijkingen, verwisselingen en rondes. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De tegels tellen vergelijkingen, verwisselingen en rondes. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.
Hoe het werkt
- Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
- Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
- Zie hoe de kleinste waarde tot nu toe verandert tijdens het zoeken, en hoe een verwisseling die aan het eind van elke ronde op zijn plek zet.
Hoe selection sort werkt
Bekijk elke waarde in de lijst en onthoud de kleinste. Verwissel die met de eerste waarde: de eerste plek is nu definitief. Doe daarna hetzelfde met de rest van de lijst, één plek verder. Na n − 1 rondes staat elke waarde op zijn plek; de laatste staat dan vanzelf goed.
Veel vergelijkingen, weinig verwisselingen
Het zoeken stopt nooit vroeg, want pas als elke overgebleven waarde bekeken is, staat vast welke de kleinste is. Daarom doet selection sort voor n waarden precies n(n − 1)/2 vergelijkingen, of de lijst nu gesorteerd, omgekeerd of willekeurig is. Daar staat tegenover dat het hoogstens n − 1 verwisselingen doet, één per ronde. Dat maakt het een redelijke keuze als een waarde verplaatsen veel duurder is dan twee waarden vergelijken.
Veelgestelde vragen
Hoe werkt selection sort?
Het kiest steeds de kleinste waarde die nog niet gesorteerd is en verwisselt die naar de eerste ongesorteerde plek. Na ronde k staan op de eerste k plekken de k kleinste waarden, op volgorde.
Hoeveel vergelijkingen en verwisselingen doet selection sort?
Altijd n(n − 1)/2 vergelijkingen voor n waarden: 45 bij 10 waarden, 780 bij 40. Het aantal verwisselingen is hoogstens n − 1, één per ronde, en minder als de kleinste waarde al op zijn plek staat.
Waarom duurt een gesorteerde lijst even lang als een omgekeerde?
Omdat elke ronde elke overgebleven waarde moet bekijken om zeker te weten dat ze de kleinste heeft gevonden. Anders dan bubblesort en insertion sort kan selection sort aan zijn vergelijkingen niet zien dat de lijst al gesorteerd is.
Is selection sort stabiel?
Niet in deze gewone vorm. Een verwisseling kan een waarde voorbij een gelijke waarde brengen: in 2, 2, 1 wisselt de eerste 2 met de 1 en komt achter de tweede 2 terecht. Een versie die waarden opschuift in plaats van verwisselt, is wel stabiel, maar verplaatst meer.
Worden mijn getallen ergens naartoe gestuurd?
Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor