Udvælgelsessortering
Udvælgelsessortering sorterer en liste, som mange sorterer kortene på hånden: find det mindste, læg det forrest, og find så det mindste af resten. Den laver mange sammenligninger men meget få ombytninger, og dens køretid afhænger næsten ikke af listens rækkefølge.
Idéen
Del listen i en sorteret del til venstre, som først er tom, og en usorteret del til højre. Gennemgå den usorterede del, og husk, hvor dens mindste værdi står. Byt den værdi med den første usorterede værdi: den sorterede del er vokset med én. Gentag, til der kun er én værdi tilbage, og den må være den største.
Et eksempel
Tag 5, 1, 4, 2, 8. Første gennemløb ser på alle fem værdier, finder 1 som den mindste og bytter den med 5: 1, 5, 4, 2, 8. Andet gennemløb ser på 5, 4, 2, 8, finder 2 og bytter den med 5: 1, 2, 4, 5, 8. Tredje gennemløb finder 4 allerede på plads, og fjerde finder 5 allerede på plads, så intet flyttes. Det giver 4 + 3 + 2 + 1 = 10 sammenligninger og kun 2 ombytninger. Boblesortering skal bruge 4 ombytninger på samme liste.
Altid lige mange sammenligninger
For at være sikker på, hvilken værdi der er mindst, skal søgningen se på hver værdi, der er tilbage. Gennemløb 1 laver n − 1 sammenligninger, gennemløb 2 laver n − 2, og så videre ned til 1, hvilket giver n(n − 1)/2 i alt. Tallet afhænger ikke af listen: en sorteret liste koster præcis lige så mange sammenligninger som en omvendt. Udvælgelsessortering kan ikke stoppe tidligt, for en søgning, der finder den mindste værdi allerede forrest, har ikke lært noget om resten.
Få ombytninger
Hvert gennemløb laver højst én ombytning, så udvælgelsessortering laver aldrig mere end n − 1 ombytninger, og den springer ombytningen over, når den mindste værdi allerede står på plads. Boblesortering og indsættelsessortering laver lige så mange ombytninger, som der er par i forkert rækkefølge, og det kan være omkring n²/2. Når det er meget dyrere at skrive en værdi end at læse to, for eksempel i hukommelse, der slides ved hver skrivning, er det lille antal ombytninger en fordel.
Ikke stabil
En sortering er stabil, når lige store værdier beholder deres oprindelige rækkefølge. Det er udvælgelsessortering ikke, for en ombytning over lang afstand kan føre en værdi forbi en lige så stor værdi. I 2, 2, 1 bytter første gennemløb det første 2-tal med 1-tallet, så man får 1, 2, 2 med de to 2-taller i omvendt rækkefølge. En version, der skubber værdierne imellem i stedet for at bytte, er stabil, men flytter langt flere værdier.
Udforsk den
Åbn appen, og tryk på Afspil, eller tryk på Trin for at gå én sammenligning ad gangen. Den værdi, der undersøges, er fremhævet, den mindste værdi indtil nu har sin egen farve, og hvert gennemløb slutter med en ombytning ind i den sorterede del til venstre. Prøv en sorteret og en omvendt liste: sammenligningerne bliver de samme, kun ombytningerne er forskellige.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for udvælgelsessortering?
O(n²) i alle tilfælde: præcis n(n − 1)/2 sammenligninger for n værdier, uanset deres rækkefølge. Den laver højst n − 1 ombytninger og kræver kun O(1) ekstra hukommelse.
Hvad er forskellen på udvælgelsessortering og boblesortering?
Boblesortering bytter naboer undervejs og kan stoppe tidligt, når et gennemløb ikke bytter noget. Udvælgelsessortering husker kun, hvor den mindste værdi står, og laver én ombytning ved slutningen af hvert gennemløb. Udvælgelsessortering laver færre ombytninger; boblesortering er hurtigere på lister, der næsten er sorteret.
Er udvælgelsessortering stabil?
Nej. En ombytning kan flytte en værdi forbi en anden, lige så stor værdi, så lige store værdier kan skifte rækkefølge. Den kan gøres stabil ved at skubbe værdier i stedet for at bytte dem, hvilket koster flere flytninger.
Hvad har heapsort med udvælgelsessortering at gøre?
Heapsort er en udvælgelsessortering med en hurtigere måde at finde den næste værdi på: den holder den usorterede del i en heap, så hver udvælgelse tager omkring log n skridt i stedet for en fuld gennemgang. Det bringer det samlede tal ned på O(n log n).
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv udvælgelsessortering