Daar is verskeie basiese algoritmes om die probleem op te los om 'n skikking te sorteer. Een van die bekendste onder hulle is invoegingssoort. As gevolg van sy duidelikheid en eenvoud, maar lae doeltreffendheid, word hierdie metode hoofsaaklik gebruik in die onderrig van programmering. Dit laat jou toe om die basiese sorteermeganismes te verstaan.
Beskrywing van die algoritme
Die kern van die invoegingssorteeralgoritme is dat 'n behoorlik geordende segment binne die aanvanklike skikking gevorm word. Elke element word een vir een met die gemerkte deel vergelyk en op die regte plek ingevoeg. Dus, nadat hulle deur al die elemente herhaal is, word hulle in die regte volgorde in lyn.
Die volgorde van seleksie van elemente kan enige wees, hulle kan arbitrêr of volgens een of ander algoritme gekies word. Meestal word opeenvolgende opsomming vanaf die begin van die skikking gebruik, waar 'n geordende segment gevorm word.
Die begin van sortering kan soos volg lyk:
- Neem die eerste element van die skikking.
- Aangesien daar niks is om dit mee te vergelyk nie, neem die element self soos bestelvolgorde.
- Gaan na die tweede item.
- Vergelyk dit met die eerste een gebaseer op die sorteerreël.
- Indien nodig, ruil elemente op plekke om.
- Neem die eerste twee elemente as 'n geordende volgorde.
- Gaan na die derde item.
- Vergelyk dit met die tweede een, ruil om indien nodig.
- As die vervanging gemaak word, vergelyk dit met die eerste een.
- Neem drie elemente as 'n geordende volgorde.
En so aan tot aan die einde van die oorspronklike skikking.
Invoeging in die werklike lewe
Vir duidelikheid is dit die moeite werd om 'n voorbeeld te gee van hoe hierdie sorteermeganisme in die alledaagse lewe gebruik word.
Neem byvoorbeeld 'n beursie. Honderd-, vyfhonderd- en duisend-dollar se banke lê in wanorde in die banknootkompartement. Dit is 'n gemors, in so 'n mengelmoes is dit moeilik om dadelik die regte stuk papier te kry. Die reeks banknote moet gesorteer word.
Die heel eerste is 'n banknoot van 1000 roebels, en onmiddellik daarna - 100. Ons neem 'n honderd en plaas dit voor. Die derde in 'n ry is 500 roebels, die regmatige plek daarvoor is tussen 'n honderd en 'n duisend.
Op dieselfde manier sorteer ons die ontvangde kaarte wanneer ons die "Fool" speel om dit makliker te maak om hulle te navigeer.
Operateurs en helperfunksies
Die invoegingssorteermetode neem as invoer 'n aanvanklike skikking wat gesorteer moet word, 'n vergelykingsfunksie, en, indien nodig, 'n funksie wat die reël vir die opsomming van elemente bepaal. Mees dikwels in plaas daarvan gebruikgereelde lusstelling.
Die eerste element is self 'n geordende stel, so die vergelyking begin vanaf die tweede.
Die algoritme gebruik dikwels 'n helperfunksie om twee waardes uit te ruil (ruil). Dit gebruik 'n bykomende tydelike veranderlike, wat geheue verbruik en die kode 'n bietjie vertraag.
'n Alternatief is om 'n groep elemente te massaverskuiwing en dan die huidige een in die vrye spasie in te voeg. In hierdie geval vind die oorgang na die volgende element plaas wanneer die vergelyking 'n positiewe resultaat gegee het, wat die korrekte volgorde aandui.
Implementasievoorbeelde
Die spesifieke implementering hang grootliks af van die programmeertaal wat gebruik word, die sintaksis en strukture daarvan.
Classic C-implementering wat 'n tydelike veranderlike gebruik om waardes uit te ruil:
int i, j, temp; vir (i=1; i =0; j--) { if (skikking[j] < temp) breek; skikking[j + 1]=skikking[j]; skikking[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; } }
Hier word eers alle elemente wat nie by die sorteervoorwaarde pas nie, na regs geskuif, en dan word die huidige element in die vrye spasie ingevoeg.
Java-kode gebruik while lus:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[vorige Sleutel]; arr[prevKey]=currElem; prevKey--; } } }
Die algemene betekenis van die kode bly onveranderd: elke element van die skikking word opeenvolgend vergelyk met die voriges en omgeruil met hulle indien nodig.
Geskatte looptyd
Natuurlik, in die beste geval, sal die invoer van die algoritme 'n skikking wees wat reeds op die regte manier georden is. In hierdie situasie sal die algoritme eenvoudig elke element moet kontroleer om seker te maak dit is op die regte plek sonder om uitruilings te maak. Dus, die looptyd sal direk afhang van die lengte van die oorspronklike skikking O(n).
Die ergste geval-invoer is 'n skikking wat in omgekeerde volgorde gesorteer is. Dit sal 'n groot aantal permutasies vereis, die looptydfunksie sal afhang van die aantal elemente kwadraat.
Die presiese aantal permutasies vir 'n heeltemal ongeordende skikking kan met die formule bereken word:
n(n-1)/2
waar n die lengte van die oorspronklike skikking is. Dit sal dus 4950 permutasies neem om 100 elemente in die korrekte volgorde te rangskik.
Die invoegmetode is baie doeltreffend om klein of gedeeltelik gesorteerde skikkings te sorteer. Dit word egter nie aanbeveel om dit oral toe te pas nie weens die hoë kompleksiteit van berekeninge.
Die algoritme word as 'n hulpmiddel in baie ander meer komplekse sorteermetodes gebruik.
Sorteer gelyke waardes
Die invoegingsalgoritme behoort aan die sogenaamde stabiele soorte. Dit beteken,dat dit nie identiese elemente omruil nie, maar hul oorspronklike volgorde behou. Die stabiliteitsindeks is in baie gevalle belangrik vir korrekte ordening.
Bogenoemde is 'n wonderlike visuele voorbeeld van invoegingssoort in 'n dans.
