Indsættelsessortering
Indsættelsessortering er sådan, de fleste sorterer en hånd kort: tag det næste kort, og skub det ind på den rigtige plads blandt de kort, der allerede ligger i rækkefølge. Den er langsom på lange tilfældige lister, men meget hurtig på korte eller næsten sorterede, og derfor bruger rigtige sorteringsbiblioteker den stadig.
Idéen
Hold starten af listen sorteret. I begyndelsen er den sorterede del kun den første værdi. Tag den næste værdi, og sammenlign den med værdien før. Er værdien før større, så byt dem, og sammenlign igen én plads længere tilbage. Stop, når værdien før ikke er større, eller når værdien når forrest. Den sorterede del er vokset med én. Gentag med hver værdi til slutningen.
Et eksempel
Tag 5, 1, 4, 2, 8. Gennemløb 1 tager 1: 5 er større, så de bytter, og 1 når forrest: 1, 5, 4, 2, 8. Gennemløb 2 tager 4: den bytter med 5 og stopper så ved 1: 1, 4, 5, 2, 8. Gennemløb 3 tager 2: den bytter med 5 og med 4 og stopper så ved 1: 1, 2, 4, 5, 8. Gennemløb 4 tager 8, som allerede er større end 5, så én sammenligning er nok. Det giver 7 sammenligninger og 4 ombytninger. Boblesortering skal bruge 9 sammenligninger på samme liste, udvælgelsessortering 10.
Ombytninger er lig med inversioner
En inversion er et par værdier i forkert rækkefølge. At bytte to naboer, der står forkert, fjerner præcis én inversion, og indsættelsessortering bytter kun sådanne naboer. Den laver altså præcis lige så mange ombytninger, som startlisten har inversioner, det samme antal som boblesortering. Hvert gennemløb laver også højst én sammenligning, der ikke fører til en ombytning, nemlig den, der stopper det. Sammenligningerne er altså inversionerne plus højst n − 1.
Adaptiv: hurtig, når listen er næsten sorteret
Fordi arbejdet er antallet af inversioner plus omkring n, er indsættelsessortering hurtig, når der er få inversioner. En sorteret liste kræver n − 1 sammenligninger og ingen ombytninger. En liste, hvor hver værdi kun står få pladser fra sin rigtige plads, tager tid tæt på n. Kun en liste langt fra sorteret, som en omvendt med n(n − 1)/2 inversioner, tager tid proportional med n². På en tilfældig liste er gennemsnittet omkring n²/4 ombytninger.
Hvor den bruges
Indsættelsessortering er stabil, kræver ingen ekstra hukommelse og har meget lidt overhead. På korte lister slår den algoritmer, der er hurtigere på papiret. Mange sorteringer i biblioteker, som Timsort i Python og Java og introsort i C++, skifter til indsættelsessortering for små stykker af listen, typisk op til et par dusin værdier. Den passer også til data, der kommer én værdi ad gangen, fordi hver ny værdi kan indsættes, så snart den kommer.
Udforsk den
Åbn appen, og tryk på Afspil, eller tryk på Trin for at gå én sammenligning ad gangen. Værdien, der indsættes, har sin egen farve, værdien, den sammenlignes med, er fremhævet, og den sorterede del er grøn. I modsætning til boblesortering og udvælgelsessortering er den grønne del ikke endelig: en senere, mindre værdi kan stadig glide ind i den. Prøv en næsten sorteret liste for at se, hvor korte gennemløbene er, og derefter en omvendt.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for indsættelsessortering?
O(n²) i værste og gennemsnitlige tilfælde og O(n) i bedste tilfælde, en liste, der allerede er sorteret. Mere præcist tager den tid proportional med n plus antallet af inversioner. Den kræver kun O(1) ekstra hukommelse.
Hvad er forskellen på indsættelsessortering og udvælgelsessortering?
Udvælgelsessortering gennemsøger hele den usorterede del for at finde den mindste værdi, så den laver altid n(n − 1)/2 sammenligninger, men få ombytninger. Indsættelsessortering tager den næste værdi, som den kommer, og flytter den kun så langt tilbage som nødvendigt, så den laver færre sammenligninger, især på næsten sorterede lister, men flere ombytninger.
Hvad er binær indsættelsessortering?
En udgave, der finder ud af, hvor den nye værdi hører hjemme, med en binær søgning i den sorterede del. Det kræver omkring log n sammenligninger i stedet for op til n. Værdierne skal stadig flyttes for at give plads, så antallet af flytninger og det værste tilfælde O(n²) forbliver det samme.
Er indsættelsessortering stabil?
Ja. En værdi flytter kun tilbage forbi værdier, der er strengt større, så ens værdier beholder deres oprindelige rækkefølge.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv indsættelsessortering