Der er flere grundlæggende algoritmer til at løse problemet med at sortere et array. En af de mest berømte blandt dem er indsættelsessortering. På grund af dens klarhed og enkelhed, men lave effektivitet, bruges denne metode hovedsageligt til undervisning i programmering. Det giver dig mulighed for at forstå de grundlæggende sorteringsmekanismer.
Beskrivelse af algoritmen
Essensen af indsættelsessorteringsalgoritmen er, at der dannes et korrekt ordnet segment inde i det indledende array. Hvert element sammenlignes et efter et med den afkrydsede del og indsættes på det rigtige sted. Efter at have gentaget alle elementerne, står de således på linje i den rigtige rækkefølge.
Rækkefølgen af udvælgelse af elementer kan være en hvilken som helst, de kan vælges vilkårligt eller ifølge en eller anden algoritme. Oftest bruges sekventiel optælling fra begyndelsen af arrayet, hvor der dannes et ordnet segment.
Begyndelsen af sorteringen kan se sådan ud:
- Tag det første element i arrayet.
- Da der ikke er noget at sammenligne det med, tag selve elementet som bestiltsekvens.
- Gå til det andet punkt.
- Sammenlign den med den første baseret på sorteringsreglen.
- Skift om nødvendigt elementer nogle steder.
- Tag de første to elementer som en ordnet sekvens.
- Gå til det tredje element.
- Sammenlign den med den anden, skift om nødvendigt.
- Hvis udskiftningen foretages, skal du sammenligne den med den første.
- Tag tre elementer som en ordnet sekvens.
Og så videre indtil slutningen af det originale array.
Real life insertion sort
For klarhedens skyld er det værd at give et eksempel på, hvordan denne sorteringsmekanisme bruges i hverdagen.
Tag for eksempel en tegnebog. Hundrede, fem hundrede og tusinde dollarsedler ligger i uorden i seddelrummet. Det er noget rod, i sådan en hodgepodge er det svært at finde det rigtige stykke papir med det samme. Rækken af pengesedler skal sorteres.
Den allerførste er en seddel på 1000 rubler, og umiddelbart efter den - 100. Vi tager et hundrede og placerer den foran. Den tredje i rækken er 500 rubler, det rette sted for den er mellem hundrede og tusinde.
På samme måde sorterer vi de modtagne kort, når vi spiller "Fool" for at gøre det nemmere at navigere i dem.
Operatører og hjælpefunktioner
Indsættelsessorteringsmetoden tager som input en indledende matrix, der skal sorteres, en sammenligningsfunktion og om nødvendigt en funktion, der bestemmer reglen for optælling af elementer. Oftest brugt i stedetalmindelig loop-erklæring.
Det første element er i sig selv et ordnet sæt, så sammenligningen starter fra det andet.
Algoritmen bruger ofte en hjælpefunktion til at udveksle to værdier (swap). Den bruger en ekstra midlertidig variabel, som bruger hukommelse og sænker koden en smule.
Et alternativ er at masseforskyde en gruppe af elementer og derefter indsætte det nuværende i det frie rum. I dette tilfælde sker overgangen til det næste element, når sammenligningen gav et positivt resultat, hvilket indikerer den korrekte rækkefølge.
Implementeringseksempler
Den specifikke implementering afhænger i høj grad af det anvendte programmeringssprog, dets syntaks og strukturer.
Classic C-implementering ved hjælp af en midlertidig variabel til at udveksle værdier:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; matrix[j + 1]=matrix[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 forskydes først alle elementer, der ikke matcher sorteringsbetingelsen, til højre, og derefter indsættes det aktuelle element i det frie rum.
Java-kode ved hjælp af while-løkke:
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 betydning af koden forbliver uændret: hvert element i arrayet sammenlignes sekventielt med de foregående og udskiftes med dem, hvis det er nødvendigt.
Estimeret køretid
Naturligvis vil inputtet af algoritmen i bedste tilfælde være et array, der allerede er ordnet på den rigtige måde. I denne situation skal algoritmen simpelthen kontrollere hvert element for at sikre, at det er på det rigtige sted uden at foretage udvekslinger. Køretiden vil således afhænge direkte af længden af det originale array O(n).
Det værst tænkelige input er et array sorteret i omvendt rækkefølge. Dette vil kræve et stort antal permutationer, runtime-funktionen vil afhænge af antallet af elementer i kvadrat.
Det nøjagtige antal permutationer for en fuldstændig uordnet matrix kan beregnes ved hjælp af formlen:
n(n-1)/2
hvor n er længden af det originale array. Således ville det tage 4950 permutationer at arrangere 100 elementer i den korrekte rækkefølge.
Indsættelsesmetoden er meget effektiv til sortering af små eller delvist sorterede arrays. Det anbefales dog ikke at anvende det over alt på grund af beregningernes høje kompleksitet.
Algorithmen bruges som et hjælpemiddel i mange andre mere komplekse sorteringsmetoder.
Sorter lige værdier
Indsættelsesalgoritmen hører til de såkaldte stabile sorteringer. Det betyder,at den ikke bytter identiske elementer, men bevarer deres oprindelige rækkefølge. Stabilitetsindekset er i mange tilfælde vigtigt for korrekt bestilling.
Ovenstående er et godt visuelt eksempel på indsættelsessortering i en dans.
