Insättningssortering
Insättningssortering är hur de flesta sorterar en hand med kort: ta upp nästa kort och skjut in det på rätt plats bland korten som redan ligger i ordning. Den är långsam på långa slumpade listor, men mycket snabb på korta eller nästan sorterade, och därför används den fortfarande i riktiga sorteringsbibliotek.
Idén
Håll början av listan sorterad. Från början är den sorterade delen bara det första värdet. Ta nästa värde och jämför det med värdet före. Om värdet före är större, byt plats på dem och jämför igen, ett steg längre bak. Stanna när värdet före inte är större, eller när värdet når första platsen. Den sorterade delen har vuxit med ett. Upprepa med varje värde till slutet.
Ett exempel
Ta 5, 1, 4, 2, 8. Varv 1 tar 1: 5 är större, så de byter plats, och 1 hamnar först: 1, 5, 4, 2, 8. Varv 2 tar 4: det byter plats med 5 och stannar sedan vid 1: 1, 4, 5, 2, 8. Varv 3 tar 2: det byter plats med 5 och med 4 och stannar sedan vid 1: 1, 2, 4, 5, 8. Varv 4 tar 8, som redan är större än 5, så en jämförelse räcker. Det blir 7 jämförelser och 4 byten. Bubbelsortering behöver 9 jämförelser på samma lista, urvalssortering 10.
Byten är lika med inversioner
En inversion är ett par värden i fel ordning. Att byta plats på två grannar som står fel tar bort exakt en inversion, och insättningssortering byter bara sådana grannar. Den gör alltså exakt lika många byten som startlistan har inversioner, samma antal som bubbelsortering. Varje varv gör också högst en jämförelse som inte leder till ett byte, den som stoppar varvet. Jämförelserna är alltså inversionerna plus högst n − 1.
Adaptiv: snabb när listan är nästan sorterad
Eftersom arbetet är antalet inversioner plus ungefär n är insättningssortering snabb så fort det finns få inversioner. En sorterad lista kräver n − 1 jämförelser och inga byten. En lista där varje värde bara står några platser från sin rätta plats tar tid nära n. Bara en lista som är långt från sorterad, som en omvänd med n(n − 1)/2 inversioner, tar tid proportionell mot n². På en slumpad lista blir det i genomsnitt ungefär n²/4 byten.
Var den används
Insättningssortering är stabil, behöver inget extra minne och har mycket lite overhead. På korta listor slår den algoritmer som är snabbare på pappret. Många sorteringar i bibliotek, som Timsort i Python och Java och introsort i C++, byter till insättningssortering för små delar av listan, oftast upp till några dussin värden. Den passar också data som kommer ett värde i taget, eftersom varje nytt värde kan sättas in så fort det kommer.
Utforska den
Öppna appen och tryck på Spela, eller tryck på Steg för att gå en jämförelse i taget. Värdet som sätts in har en egen färg, värdet det jämförs med är markerat och den sorterade delen är grön. Till skillnad från bubbelsortering och urvalssortering är den gröna delen inte slutlig: ett senare, mindre värde kan fortfarande glida in i den. Prova en nästan sorterad lista för att se hur korta varven är, och sedan en omvänd.
Ofta ställda frågor
Vilken tidskomplexitet har insättningssortering?
O(n²) i värsta fallet och i genomsnitt, och O(n) i bästa fallet, en lista som redan är sorterad. Mer exakt tar den tid proportionell mot n plus antalet inversioner. Den behöver bara O(1) extra minne.
Vad är skillnaden mellan insättningssortering och urvalssortering?
Urvalssortering söker igenom hela den osorterade delen för att hitta det minsta värdet, så den gör alltid n(n − 1)/2 jämförelser men få byten. Insättningssortering tar nästa värde som det kommer och flyttar det bara så långt bakåt som behövs, så den gör färre jämförelser, särskilt på nästan sorterade listor, men fler byten.
Vad är binär insättningssortering?
En variant som tar reda på var det nya värdet hör hemma med en binärsökning i den sorterade delen, vilket kräver ungefär log n jämförelser i stället för upp till n. Värdena måste fortfarande flyttas för att ge plats, så antalet förflyttningar, och värsta fallet O(n²), förblir desamma.
Är insättningssortering stabil?
Ja. Ett värde flyttar bara bakåt förbi värden som är strikt större, så lika värden behåller sin ursprungliga ordning.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova insättningssortering