Massiivi sortimise probleemi lahendamiseks on mitu põhialgoritmi. Üks kuulsamaid neist on sisestamise sortimine. Selguse ja lihtsuse, kuid madala efektiivsuse tõttu kasutatakse seda meetodit peamiselt programmeerimise õpetamisel. See võimaldab teil mõista põhilisi sortimismehhanisme.
Algoritmi kirjeldus
Sisestamise sortimise algoritmi põhiolemus seisneb selles, et algmassiivi sees moodustatakse õigesti järjestatud segment. Iga elementi võrreldakse ükshaaval kontrollitud osaga ja sisestatakse õigesse kohta. Seega, pärast kõigi elementide läbimist reastuvad need õiges järjekorras.
Elementide valimise järjekord võib olla mis tahes, neid saab valida suvaliselt või mõne algoritmi järgi. Kõige sagedamini kasutatakse järjestikust loendust massiivi algusest, kus moodustatakse järjestatud segment.
Sortimise algus võib välja näha selline:
- Võtke massiivi esimene element.
- Kuna seda pole millegagi võrrelda, võtke element ise nagu tellitudjärjestus.
- Mine teise üksuse juurde.
- Võrdle seda sortimisreegli alusel esimesega.
- Vajadusel vahetage elemente kohtades.
- Võtke kaks esimest elementi järjestatud jadana.
- Mine kolmanda üksuse juurde.
- Võrdle seda teisega, vajadusel vaheta.
- Kui asendus tehakse, võrrelge seda esimesega.
- Võtke kolm elementi järjestatud jadana.
Ja nii edasi kuni algse massiivi lõpuni.
Reaalse elu sisestuse sortimine
Selguse huvides tasub tuua näide, kuidas seda sorteerimismehhanismi igapäevaelus kasutatakse.
Võtke näiteks rahakott. Saja-, viiesaja- ja tuhandedollarilised kupüürid lebavad rahatähtede lahtris segaduses. See on jama, sellises kägaras on raske kohe õiget paberit leida. Pangatähtede massiiv peab olema sorteeritud.
Kõige esimene on 1000-rublane rahatäht ja kohe pärast seda - 100. Võtame sada ja asetame selle ette. Järjekorras kolmas on 500 rubla, selle õige koht jääb saja ja tuhande vahele.
Samamoodi sorteerime vastuvõetud kaardid "Lolli" mängimisel, et oleks lihtsam nendes navigeerida.
Operaatorid ja abifunktsioonid
Sisestamise sortimise meetod võtab sisendiks algse sortitava massiivi, võrdlusfunktsiooni ja vajaduse korral funktsiooni, mis määrab elementide loendamise reegli. Kõige sagedamini kasutatakse selle asemeltavalise tsükli lause.
Esimene element on ise järjestatud komplekt, nii et võrdlus algab teisest.
Algoritm kasutab kahe väärtuse vahetamiseks (vahetus) sageli abifunktsiooni. See kasutab täiendavat ajutist muutujat, mis kulutab mälu ja aeglustab koodi veidi.
Alternatiiviks on elementide rühma massiline nihutamine ja seejärel praeguse elemendi sisestamine vabasse ruumi. Sel juhul toimub üleminek järgmisele elemendile, kui võrdlus andis positiivse tulemuse, mis näitab õiget järjekorda.
Rakenduse näited
Konkreetne teostus sõltub suuresti kasutatavast programmeerimiskeelest, selle süntaksist ja struktuuridest.
Classic C juurutamine, kasutades väärtuste vahetamiseks ajutist muutujat:
int i, j, temp; for (i=1; i =0; j--) { if (massiivi[j] < temp) break; massiiv[j + 1]=massiiv[j]; massiiv[j]=temp; } }
PHP juurutamine:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Siin nihutatakse kõigepe alt kõik elemendid, mis ei vasta sortimistingimustele, paremale ja seejärel sisestatakse praegune element vabasse ruumi.
Java-kood, kasutades while-tsüklit:
avalik staatiline void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[eelmineKey+1]=arr[eelmineKey]; arr[eelmineKey]=currElem; prevKey--; } } }
Koodi üldine tähendus jääb muutumatuks: iga massiivi elementi võrreldakse järjestikku eelmistega ja vajadusel vahetatakse nendega.
Eeldatav tööaeg
Ilmselt parimal juhul on algoritmi sisendiks juba õigel viisil järjestatud massiiv. Sellises olukorras peab algoritm lihts alt kontrollima iga elementi, veendumaks, et see on õiges kohas, ilma vahetusi tegemata. Seega sõltub tööaeg otseselt algse massiivi pikkusest O(n).
Halvimal juhul on massiiv, mis on sorteeritud vastupidises järjekorras. See nõuab suurt hulka permutatsioone, käitusaja funktsioon sõltub elementide arvust ruudus.
Täiesti järjestamata massiivi permutatsioonide täpse arvu saab arvutada järgmise valemi abil:
n(n-1)/2
kus n on algse massiivi pikkus. Seega kuluks 100 elemendi õiges järjekorras korraldamiseks 4950 permutatsiooni.
Sisestamismeetod on väikeste või osaliselt sorteeritud massiivide sortimiseks väga tõhus. Arvutuste suure keerukuse tõttu ei soovita seda aga kõikjal rakendada.
Algoritmi kasutatakse abivahendina paljudes teistes keerukamates sortimismeetodites.
Sordi võrdsed väärtused
Sisestamisalgoritm kuulub nn stabiilsete sortide hulka. See tähendab,et see ei vaheta identseid elemente, vaid säilitab nende esialgse järjekorra. Stabiilsusindeks on paljudel juhtudel õige järjestuse jaoks oluline.
Ül altoodu on suurepärane visuaalne näide sisestussortimisest tantsus.
