Er zijn verschillende basisalgoritmen om het probleem van het sorteren van een array op te lossen. Een van de meest bekende onder hen is invoegsoort. Vanwege de duidelijkheid en eenvoud, maar lage efficiëntie, wordt deze methode voornamelijk gebruikt bij het aanleren van programmeren. Het stelt u in staat om de basissorteermechanismen te begrijpen.
Beschrijving van het algoritme
De essentie van het insertion sort-algoritme is dat een correct geordend segment wordt gevormd binnen de initiële array. Elk element wordt één voor één vergeleken met het aangevinkte onderdeel en op de juiste plaats ingevoegd. Dus, na het doorlopen van alle elementen, komen ze in de juiste volgorde te staan.
De volgorde van het selecteren van elementen kan elke zijn, ze kunnen willekeurig of volgens een of ander algoritme worden geselecteerd. Meestal wordt sequentiële opsomming gebruikt vanaf het begin van de array, waar een geordend segment wordt gevormd.
Het begin van het sorteren kan er als volgt uitzien:
- Neem het eerste element van de array.
- Aangezien er niets is om het mee te vergelijken, neem het element zelf zoals besteldvolgorde.
- Ga naar het tweede item.
- Vergelijk het met de eerste op basis van de sorteerregel.
- Verwissel indien nodig elementen van plaats.
- Neem de eerste twee elementen als een geordende reeks.
- Ga naar het derde item.
- Vergelijk het met de tweede, verwissel indien nodig.
- Als de vervanging is gemaakt, vergelijk deze dan met de eerste.
- Neem drie elementen als een geordende reeks.
En zo verder tot het einde van de originele array.
Invoeging in het echte leven
Voor de duidelijkheid is het de moeite waard een voorbeeld te geven van hoe dit sorteermechanisme in het dagelijks leven wordt gebruikt.
Neem bijvoorbeeld een portemonnee. Honderd, vijfhonderd en duizend dollarbiljetten liggen in wanorde in het bankbiljettenvak. Dit is een rommeltje, in zo'n mengelmoes is het lastig om meteen het juiste papiertje te vinden. De reeks bankbiljetten moet worden gesorteerd.
De allereerste is een bankbiljet van 1000 roebel, en onmiddellijk daarna - 100. We nemen honderd en plaatsen het vooraan. De derde op rij is 500 roebel, de rechtmatige plaats daarvoor is tussen de honderd en duizend.
Op dezelfde manier sorteren we de ontvangen kaarten bij het spelen van de "Fool" om het gemakkelijker te maken om ze te navigeren.
Operators en helperfuncties
De insertion sort-methode heeft als invoer een initiële array die moet worden gesorteerd, een vergelijkingsfunctie en, indien nodig, een functie die de regel bepa alt voor het opsommen van elementen. Meestal gebruikt in plaats daarvanreguliere lus-instructie.
Het eerste element is zelf een geordende verzameling, dus de vergelijking begint bij het tweede.
Het algoritme gebruikt vaak een helperfunctie om twee waarden uit te wisselen (swap). Het gebruikt een extra tijdelijke variabele, die geheugen verbruikt en de code een beetje vertraagt.
Een alternatief is om een groep elementen massaal te verschuiven en vervolgens de huidige in de vrije ruimte in te voegen. In dit geval vindt de overgang naar het volgende element plaats wanneer de vergelijking een positief resultaat opleverde, wat de juiste volgorde aangeeft.
Implementatievoorbeelden
De specifieke implementatie hangt grotendeels af van de gebruikte programmeertaal, de syntaxis en structuren.
Klassieke C-implementatie die een tijdelijke variabele gebruikt om waarden uit te wisselen:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; array[j + 1]=array[j]; array[j]=temperatuur; } }
PHP-implementatie:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Hier worden eerst alle elementen die niet overeenkomen met de sorteervoorwaarde naar rechts verschoven en vervolgens wordt het huidige element in de vrije ruimte ingevoegd.
Java-code met while-lus:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[vorigeSleutel]; arr[prevKey]=currElem; prevKey--; } } }
De algemene betekenis van de code blijft ongewijzigd: elk element van de array wordt opeenvolgend vergeleken met de vorige en indien nodig verwisseld.
Geschatte looptijd
Het is duidelijk dat in het beste geval de invoer van het algoritme een array is die al op de juiste manier is geordend. In deze situatie moet het algoritme eenvoudig elk element controleren om er zeker van te zijn dat het op de juiste plaats staat zonder uitwisselingen. De looptijd is dus direct afhankelijk van de lengte van de originele array O(n).
De invoer in het slechtste geval is een array die in omgekeerde volgorde is gesorteerd. Dit vereist een groot aantal permutaties, de runtime-functie hangt af van het aantal elementen in het kwadraat.
Het exacte aantal permutaties voor een volledig ongeordende array kan worden berekend met behulp van de formule:
n(n-1)/2
waarbij n de lengte is van de oorspronkelijke array. Er zijn dus 4950 permutaties nodig om 100 elementen in de juiste volgorde te rangschikken.
De invoegmethode is zeer efficiënt voor het sorteren van kleine of gedeeltelijk gesorteerde arrays. Het wordt echter niet aanbevolen om het overal toe te passen vanwege de hoge complexiteit van berekeningen.
Het algoritme wordt gebruikt als hulpmiddel bij veel andere, meer complexe sorteermethoden.
Sorteer gelijke waarden
Het invoegalgoritme behoort tot de zogenaamde stabiele sorteringen. Het betekent,dat het identieke elementen niet verwisselt, maar hun oorspronkelijke volgorde behoudt. De stabiliteitsindex is in veel gevallen belangrijk voor een juiste volgorde.
Het bovenstaande is een geweldig visueel voorbeeld van invoegsortering in een dans.
