Det finnes flere grunnleggende algoritmer for å løse problemet med å sortere en matrise. En av de mest kjente blant dem er innsettingssortering. På grunn av sin klarhet og enkelhet, men lave effektivitet, brukes denne metoden hovedsakelig i undervisning i programmering. Den lar deg forstå de grunnleggende sorteringsmekanismene.
Beskrivelse av algoritmen
Kjernen i innsettingssorteringsalgoritmen er at et riktig ordnet segment dannes inne i den innledende matrisen. Hvert element sammenlignes en etter en med den sjekkede delen og settes inn på riktig sted. Etter å ha iterert gjennom alle elementene, stiller de derfor opp i riktig rekkefølge.
Rekkefølgen for å velge elementer kan være hvilken som helst, de kan velges vilkårlig eller i henhold til en eller annen algoritme. Oftest brukes sekvensiell opptelling fra begynnelsen av matrisen, hvor et ordnet segment dannes.
Begynnelsen av sorteringen kan se slik ut:
- Ta det første elementet i matrisen.
- Siden det ikke er noe å sammenligne det med, ta selve elementet som bestiltsekvens.
- Gå til det andre elementet.
- Sammenlign den med den første basert på sorteringsregelen.
- Om nødvendig, bytt elementer på steder.
- Ta de to første elementene som en ordnet sekvens.
- Gå til det tredje elementet.
- Sammenlign den med den andre, bytt om nødvendig.
- Hvis erstatningen er gjort, sammenlign den med den første.
- Ta tre elementer som en ordnet sekvens.
Og så videre til slutten av den originale matrisen.
Real life insertion sort
For klarhetens skyld er det verdt å gi et eksempel på hvordan denne sorteringsmekanismen brukes i hverdagen.
Ta for eksempel en lommebok. Hundre-, fem-hundre- og tusenlapper ligger i uorden i seddelrommet. Dette er et rot, i en slik hodgepodge er det vanskelig å umiddelbart finne det riktige stykket papir. Serien med sedler må sorteres.
Den aller første er en seddel på 1000 rubler, og rett etter den - 100. Vi tar en hundre og legger den foran. Den tredje i rekken er 500 rubler, den rettmessige plassen for den er mellom hundre og tusen.
På samme måte sorterer vi de mottatte kortene når vi spiller "Fool" for å gjøre det lettere å navigere i dem.
Operatører og hjelpefunksjoner
Sorteringsmetoden for innsetting tar som input en innledende matrise som skal sorteres, en sammenligningsfunksjon og, om nødvendig, en funksjon som bestemmer regelen for opptelling av elementer. Oftest brukt i stedetvanlig loop-uttalelse.
Det første elementet er i seg selv et ordnet sett, så sammenligningen starter fra det andre.
Algoritmen bruker ofte en hjelpefunksjon for å bytte ut to verdier (swap). Den bruker en ekstra midlertidig variabel, som bruker minne og bremser koden litt.
Et alternativ er å masseforskyve en gruppe elementer og deretter sette inn den gjeldende i det ledige rommet. I dette tilfellet skjer overgangen til neste element når sammenligningen ga et positivt resultat, som indikerer riktig rekkefølge.
Implementeringseksempler
Den spesifikke implementeringen avhenger i stor grad av programmeringsspråket som brukes, dets syntaks og strukturer.
Classic C-implementering som bruker en midlertidig variabel for å utveksle verdier:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; matrise[j + 1]=matrise[j]; array[j]=temp; } }
PHP-implementering:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Her forskyves først alle elementer som ikke samsvarer med sorteringsbetingelsen til høyre, og deretter settes det gjeldende elementet inn i det ledige rommet.
Java-kode som bruker while loop:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Den generelle betydningen av koden forblir uendret: hvert element i matrisen sammenlignes sekvensielt med de forrige og byttes med dem om nødvendig.
Estimert kjøretid
Åpenbart, i beste fall vil inngangen til algoritmen være en matrise som allerede er ordnet på riktig måte. I denne situasjonen må algoritmen ganske enkelt sjekke hvert element for å sikre at det er på rett sted uten å gjøre utvekslinger. Dermed vil kjøretiden direkte avhenge av lengden på den opprinnelige matrisen O(n).
Det verste tilfellet er en matrise sortert i omvendt rekkefølge. Dette vil kreve et stort antall permutasjoner, kjøretidsfunksjonen vil avhenge av antall elementer i kvadrat.
Det nøyaktige antallet permutasjoner for en fullstendig uordnet matrise kan beregnes ved å bruke formelen:
n(n-1)/2
der n er lengden på den opprinnelige matrisen. Dermed ville det ta 4950 permutasjoner for å ordne 100 elementer i riktig rekkefølge.
Innsettingsmetoden er svært effektiv for sortering av små eller delvis sorterte arrays. Det anbefales imidlertid ikke å bruke det over alt på grunn av den høye kompleksiteten til beregninger.
Algoritmen brukes som et hjelpemiddel i mange andre mer komplekse sorteringsmetoder.
Sorter like verdier
Innsettingsalgoritmen tilhører de såk alte stabile sorteringene. Det betyr,at den ikke bytter identiske elementer, men bevarer deres opprinnelige rekkefølge. Stabilitetsindeksen er i mange tilfeller viktig for riktig rekkefølge.
Ovennevnte er et flott visuelt eksempel på innsettingssortering i en dans.
