Det finns flera grundläggande algoritmer för att lösa problemet med att sortera en array. En av de mest kända bland dem är insättningssortering. På grund av dess tydlighet och enkelhet, men låga effektivitet, används denna metod främst i undervisning i programmering. Det låter dig förstå de grundläggande sorteringsmekanismerna.
Beskrivning av algoritmen
Käran av insättningssorteringsalgoritmen är att ett korrekt ordnat segment bildas inuti den initiala arrayen. Varje element jämförs ett efter ett med den markerade delen och sätts in på rätt plats. Efter att ha itererat igenom alla element, ställs de upp i rätt ordning.
Ordningen för att välja element kan vara vilken som helst, de kan väljas godtyckligt eller enligt någon algoritm. Oftast används sekventiell uppräkning från början av arrayen, där ett ordnat segment bildas.
Början av sorteringen kan se ut så här:
- Ta det första elementet i arrayen.
- Eftersom det inte finns något att jämföra med, ta själva elementet som beställtsekvens.
- Gå till det andra objektet.
- Jämför det med det första baserat på sorteringsregeln.
- Om det behövs, byt element på platser.
- Ta de två första elementen som en ordnad sekvens.
- Gå till det tredje objektet.
- Jämför det med det andra, byt om det behövs.
- Om bytet görs, jämför det med det första.
- Ta tre element som en ordnad sekvens.
Och så vidare till slutet av den ursprungliga arrayen.
Införande i verkligheten
För tydlighetens skull är det värt att ge ett exempel på hur denna sorteringsmekanism används i vardagen.
Ta till exempel en plånbok. Hundra, femhundra och tusenlappar ligger i oordning i sedelfacket. Det här är en röra, i en sådan hodgepodge är det svårt att omedelbart hitta rätt papper. Uppsättningen av sedlar måste sorteras.
Den allra första är en sedel på 1000 rubel, och omedelbart efter den - 100. Vi tar en hundra och placerar den framför. Den tredje i raden är 500 rubel, den rättmätiga platsen för den är mellan hundra och tusen.
På samma sätt sorterar vi de mottagna korten när vi spelar "Fool" för att göra det lättare att navigera i dem.
Operatörer och hjälpfunktioner
Insättningssorteringsmetoden tar som indata en initial array som ska sorteras, en jämförelsefunktion och, om nödvändigt, en funktion som bestämmer regeln för uppräkning av element. Används oftast iställetvanlig loop-sats.
Det första elementet är i sig en ordnad uppsättning, så jämförelsen börjar från den andra.
Algorithmen använder ofta en hjälpfunktion för att byta ut två värden (swap). Den använder ytterligare en temporär variabel, som förbrukar minne och saktar ner koden en aning.
Ett alternativ är att massförskjuta en grupp av element och sedan infoga den nuvarande i det fria utrymmet. I detta fall sker övergången till nästa element när jämförelsen gav ett positivt resultat, vilket indikerar rätt ordning.
Implementeringsexempel
Den specifika implementeringen beror till stor del på vilket programmeringsspråk som används, dess syntax och strukturer.
Classic C-implementering med en temporär variabel för att utbyta värden:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; array[j + 1]=array[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; } }
Här förskjuts först alla element som inte matchar sorteringsvillkoret till höger, och sedan infogas det aktuella elementet i det fria utrymmet.
Java-kod använder 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--; } } }
Kodens allmänna innebörd förblir oförändrad: varje element i arrayen jämförs sekventiellt med de föregående och byts ut med dem vid behov.
Uppskattad gångtid
Självklart, i bästa fall kommer inmatningen av algoritmen att vara en array som redan är ordnad på rätt sätt. I den här situationen måste algoritmen helt enkelt kontrollera varje element för att se till att det är på rätt plats utan att göra utbyten. Sålunda kommer körtiden direkt att bero på längden på den ursprungliga arrayen O(n).
Det värsta fallet är en matris sorterad i omvänd ordning. Detta kommer att kräva ett stort antal permutationer, körtidsfunktionen kommer att bero på antalet element i kvadrat.
Det exakta antalet permutationer för en helt oordnad array kan beräknas med formeln:
n(n-1)/2
där n är längden på den ursprungliga matrisen. Således skulle det ta 4950 permutationer för att ordna 100 element i rätt ordning.
Infogningsmetoden är mycket effektiv för att sortera små eller delvis sorterade arrayer. Det rekommenderas dock inte att använda det överallt på grund av den höga komplexiteten i beräkningarna.
Algorithmen används som ett hjälpmedel i många andra mer komplexa sorteringsmetoder.
Sortera lika värden
Infogningsalgoritmen tillhör de så kallade stabila sorteringarna. Det betyder,att den inte byter identiska element, utan bevarar deras ursprungliga ordning. Stabilitetsindex är i många fall viktigt för korrekt ordning.
Ovanstående är ett bra visuellt exempel på insättningssortering i en dans.
