Sammenligninger
Ombytninger
Gennemløb

  • Sammenlignet
  • Mindste indtil nu
  • Byttet
  • På plads

Mere om udvælgelsessortering

Udvælgelsessortering

Udvælgelsessortering bygger den sorterede liste op forfra. Hvert gennemløb gennemgår de værdier, der endnu ikke er sorteret, holder styr på den mindste og bytter den ind på den første usorterede plads. Afspil sorteringen i den hastighed, du vil, eller gå igennem den én sammenligning ad gangen, og følg tællerne for sammenligninger, ombytninger og gennemløb. Tryk på Afspil for at se sorteringen, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Felterne tæller sammenligninger, ombytninger og gennemløb. Vælg hvor mange søjler, hvordan de starter, eller skriv dine egne tal. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.

Sådan virker det

  1. Vælg hvor mange søjler og hvordan de starter: tilfældigt, næsten sorteret, omvendt eller med få unikke værdier. Eller skriv dine egne tal.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
  3. Se den mindste værdi indtil nu skifte undervejs i søgningen, og ombytningen, der sætter den på plads ved slutningen af hvert gennemløb.

Sådan virker udvælgelsessortering

Se på hver værdi i listen, og husk den mindste. Byt den med den første værdi: den første plads er nu endelig. Gør så det samme med resten af listen, én plads længere fremme. Efter n − 1 gennemløb står alle værdier på plads, og den sidste står automatisk på plads.

Mange sammenligninger, få ombytninger

Søgningen stopper aldrig tidligt, for først når den har set alle tilbageværende værdier, kan den vide, hvilken der er mindst. Derfor laver udvælgelsessortering præcis n(n − 1)/2 sammenligninger for n værdier, uanset om listen er sorteret, omvendt eller tilfældig. Til gengæld laver den højst n − 1 ombytninger, én pr. gennemløb. Det gør den til et fornuftigt valg, når det koster langt mere at flytte en værdi end at sammenligne to.

Ofte stillede spørgsmål

Hvordan virker udvælgelsessortering?

Den udvælger gang på gang den mindste værdi, der endnu ikke er sorteret, og bytter den ind på den første usorterede plads. Efter gennemløb k indeholder de første k pladser de k mindste værdier i rækkefølge.

Hvor mange sammenligninger og ombytninger laver udvælgelsessortering?

Altid n(n − 1)/2 sammenligninger for n værdier: 45 for 10 værdier, 780 for 40. Antallet af ombytninger er højst n − 1, én pr. gennemløb, og færre når den mindste værdi allerede står på plads.

Hvorfor tager en sorteret liste lige så lang tid som en omvendt?

Fordi hvert gennemløb skal se på alle tilbageværende værdier for at være sikker på, at det har fundet den mindste. I modsætning til boblesortering og indsættelsessortering kan udvælgelsessortering ikke se ud fra sine sammenligninger, at listen allerede er sorteret.

Er udvælgelsessortering stabil?

Ikke i den almindelige form. En ombytning kan føre en værdi forbi en lige så stor værdi: i 2, 2, 1 bytter det første 2-tal med 1-tallet og ender bag det andet 2-tal. En version, der skubber værdier i stedet for at bytte dem, er stabil, men kræver flere flytninger.

Bliver mine tal sendt nogen steder hen?

Nej. Sorteringen kører i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor