Insättningssortering
↑Snabböversikt
Section titled “Snabböversikt”Insättningssortering bygger upp en sorterad del av listan, ett värde i taget. Metoden är enkel och fungerar bra på små eller nästan sorterade listor.
| Egenskap | Kom ihåg |
|---|---|
| Vanlig tidskomplexitet | O(n²) |
| Extra minne | O(1) |
| Stabil? | Ja, med implementationen nedan |
| Passar bäst när | Listan är liten eller nästan sorterad |
Se algoritmen arbeta
Section titled “Se algoritmen arbeta”Staplarna visar värden och positioner. Välj Nästa för att undersöka ett moment eller Spela för hela förloppet. Testa egna tal, gärna en redan sorterad och en omvänt sorterad lista.
Beskriv själv vad algoritmen gör just nu.
Varför behövs det här steget?
Försök förutse nästa steg.
Lila: jämförs eller flyttas | Grönt: färdig del | Orange: aktuellt arbetsområde
Steg för steg
Section titled “Steg för steg”- Börja på index 1. Betrakta det första elementet som en redan sorterad del.
- Spara värdet. Det kallas nyckeln. Då kan andra element flyttas utan att nyckeln försvinner.
- Sök åt vänster. Jämför nyckeln med värdet direkt till vänster.
- Flytta större värden. Skjut varje större värde ett steg åt höger så att en ledig plats uppstår.
- Sätt in nyckeln. Stanna när du når början eller hittar ett värde som är mindre än eller lika med nyckeln.
- Upprepa. Den sorterade delen växer med ett element per varv.
Följ ett litet exempel för hand
Section titled “Följ ett litet exempel för hand”Med [7, 3, 5] börjar vi med [7]. Sätt in 3 före 7: [3, 7, 5]. Jämför sedan 5 med 7, flytta 7 åt höger och sätt in 5 efter 3. Resultatet blir [3, 5, 7].
Implementation i C#
Section titled “Implementation i C#”static void InsertionSort(int[] values){ for (int i = 1; i < values.Length; i++) { int key = values[i]; int j = i - 1;
while (j >= 0 && values[j] > key) { values[j + 1] = values[j]; j--; }
values[j + 1] = key; }}#include <vector>void insertionSort(std::vector<int>& values) { for (std::size_t i = 1; i < values.size(); ++i) { int key = values[i]; int j = static_cast<int>(i) - 1; while (j >= 0 && values[j] > key) { values[j + 1] = values[j]; --j; } values[j + 1] = key; }}Komplexitet och avvägningar
Section titled “Komplexitet och avvägningar”| Mått | Kostnad | Förklaring |
|---|---|---|
| Bästa fall | O(n) |
En redan sorterad lista behöver få jämförelser. |
| Genomsnitt | O(n²) |
Många nycklar behöver flyttas genom den sorterade delen. |
| Sämsta fall | O(n²) |
Omvänd ordning kräver flest flyttningar. |
| Extra minne | O(1) |
Indata ändras på plats. |
| Stabilitet | Stabil | Lika värden flyttas inte förbi varandra. |
En nästan sorterad lista kräver vanligtvis färre förflyttningar. För stora osorterade listor blir den kvadratiska tidsåtgången ofta för dyr.
Vanliga misstag
Section titled “Vanliga misstag”- Att glömma spara nyckeln innan element flyttas.
- Att läsa ett negativt index när sökningen når början.
- Att använda
>=i villkoret och därmed flytta lika värden förbi varandra.
Vad garanterar den sorterade delen?
Section titled “Vad garanterar den sorterade delen?”Efter varje yttre iteration är de första i + 1 objekten sorterade. Det är algoritmens viktigaste invariant. Resten behöver ännu inte vara sorterad. Nästa värde placeras in genom att större värden skjuts ett steg åt höger. Därför fungerar metoden ofta bra när indata nästan redan är i ordning.
När passar insättningssortering?
Section titled “När passar insättningssortering?”Algoritmen är enkel, arbetar på plats och kan vara stabil. Den är användbar för korta listor eller små delar inom en mer avancerad sorteringsmetod. På stora osorterade listor blir arbetet däremot ofta kvadratiskt.
Dubbletter och stabilitet
Section titled “Dubbletter och stabilitet”Villkoret values[j] > key flyttar inte värden som är lika med key. Därför bevaras deras inbördes ordning. Byter du till >= kan ordningen mellan lika värden ändras.