- Sätts in
- Jämförda
- Bytta
- Sorterad del
Insättningssortering
Insättningssortering fungerar som när många sorterar spelkort på handen. Den håller en sorterad del längst fram i listan, tar nästa värde och skjuter det bakåt förbi varje större värde tills det passar. Spela upp sorteringen i valfri hastighet, eller stega igenom den en jämförelse i taget, och följ räknarna för jämförelser, byten och varv. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst. Rutorna räknar jämförelser, byten och varv. Välj hur många staplar, hur de börjar, eller skriv dina egna tal. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Välj antal staplar och startordning: slumpad, nästan sorterad, omvänd eller med få unika värden. Eller skriv dina egna tal.
- Tryck på Spela, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
- Prova en nästan sorterad lista och en omvänd, och jämför hur många jämförelser var och en kräver.
Så fungerar insättningssortering
Det första värdet för sig är en sorterad del. Ta det andra värdet och jämför det med värdet före; om värdet före är större, byt plats på dem, och fortsätt jämföra och byta tills värdet före inte är större eller värdet når första platsen. Nu står de två första värdena i ordning. Gör likadant med det tredje värdet, det fjärde och så vidare till listans slut.
Snabb på nästan sorterade listor
Varje varv stannar vid det första värdet som inte är större, så ett värde som redan står nära sin plats kostar bara en eller två jämförelser. En sorterad lista kräver n − 1 jämförelser och inga byten; en omvänd lista, värsta fallet, kräver n(n − 1)/2 av varje. Antalet byten är alltid lika med antalet inversioner i startlistan, alltså paren som ligger i fel ordning. Därför används insättningssortering ofta för korta eller nästan sorterade listor, och inuti snabbare sorteringar för att göra klart små delar.
Ofta ställda frågor
Hur fungerar insättningssortering?
Den bygger upp en sorterad del längst fram i listan. Varje varv tar nästa värde och flyttar det bakåt förbi varje större värde före det, tills det passar. Efter varv k står de första k + 1 värdena i ordning, men ett senare värde kan fortfarande sättas in mellan dem.
Hur många jämförelser och byten gör insättningssortering?
Antalet byten är alltid lika med antalet inversioner i startlistan: inga för en sorterad lista, n(n − 1)/2 för en omvänd. Jämförelserna är bytena plus högst en per varv, alltså mellan n − 1 och n(n − 1)/2.
Varför är insättningssortering snabb på nästan sorterade listor?
För att ett varv stannar så snart det möter ett värde som inte är större. När varje värde står nära sin slutliga plats är varje varv kort, och hela sorteringen tar tid nära n.
Är insättningssortering stabil?
Ja. Ett värde flyttar bara förbi värden som är strikt större, så lika värden passerar aldrig varandra och behåller sin ursprungliga ordning.
Skickas mina tal någonstans?
Nej. Sorteringen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor