Sammenligninger
Ombytninger
Gennemløb

  • Indsættes
  • Sammenlignet
  • Byttet
  • Sorteret del

Mere om indsættelsessortering

Indsættelsessortering

Indsættelsessortering virker, som mange sorterer spillekort på hånden. Den holder en sorteret del forrest i listen, tager den næste værdi og skubber den tilbage forbi hver større værdi, indtil den passer. 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. Prøv en næsten sorteret liste og en omvendt, og sammenlign, hvor mange sammenligninger hver kræver.

Sådan virker indsættelsessortering

Den første værdi alene er en sorteret del. Tag den anden værdi, og sammenlign den med den før; er den før større, så byt dem, og bliv ved med at sammenligne og bytte, indtil værdien før ikke er større, eller værdien når forrest. Nu står de to første værdier i rækkefølge. Gør det samme med den tredje værdi, den fjerde og så videre til listens slutning.

Hurtig på næsten sorterede lister

Hvert gennemløb stopper ved den første værdi, der ikke er større, så en værdi, der allerede står tæt på sin plads, koster kun en sammenligning eller to. En sorteret liste kræver n − 1 sammenligninger og ingen ombytninger; en omvendt liste, det værste tilfælde, kræver n(n − 1)/2 af hver. Antallet af ombytninger er altid lig med antallet af inversioner i startlisten, altså de par, der står i forkert rækkefølge. Derfor bruges indsættelsessortering ofte til korte eller næsten sorterede lister og inde i hurtigere sorteringer til at gøre små stykker færdige.

Ofte stillede spørgsmål

Hvordan virker indsættelsessortering?

Den bygger en sorteret del op forrest i listen. Hvert gennemløb tager den næste værdi og flytter den tilbage forbi hver større værdi foran den, indtil den passer. Efter gennemløb k står de første k + 1 værdier i rækkefølge, men en senere værdi kan stadig indsættes imellem dem.

Hvor mange sammenligninger og ombytninger laver indsættelsessortering?

Antallet af ombytninger er altid lig med antallet af inversioner i startlisten: ingen for en sorteret liste, n(n − 1)/2 for en omvendt. Sammenligningerne er ombytningerne plus højst én pr. gennemløb, altså mellem n − 1 og n(n − 1)/2.

Hvorfor er indsættelsessortering hurtig på næsten sorterede lister?

Fordi et gennemløb stopper, så snart det møder en værdi, der ikke er større. Når hver værdi står tæt på sin endelige plads, er hvert gennemløb kort, og hele sorteringen tager tid tæt på n.

Er indsættelsessortering stabil?

Ja. En værdi flytter kun forbi værdier, der er strengt større, så ens værdier passerer aldrig hinanden og beholder deres oprindelige rækkefølge.

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