Ir vairāki pamata algoritmi, lai atrisinātu masīva kārtošanas problēmu. Viens no slavenākajiem starp tiem ir ievietošanas kārtošana. Savas skaidrības un vienkāršības, bet zemās efektivitātes dēļ šī metode tiek izmantota galvenokārt programmēšanas mācībā. Tas ļauj izprast pamata šķirošanas mehānismus.
Algoritma apraksts
Ievietošanas kārtošanas algoritma būtība ir tāda, ka sākotnējā masīvā tiek izveidots pareizi sakārtots segments. Katrs elements tiek salīdzināts pa vienam ar pārbaudīto daļu un ievietots pareizajā vietā. Tādējādi pēc visu elementu atkārtošanas tie sarindojas pareizajā secībā.
Elementu atlases secība var būt jebkura, tos var atlasīt patvaļīgi vai pēc kāda algoritma. Visbiežāk tiek izmantota secīgā uzskaite no masīva sākuma, kur tiek veidots sakārtots segments.
Kārtošanas sākums varētu izskatīties šādi:
- Ņemiet pirmo masīva elementu.
- Tā kā nav ar ko salīdzināt, ņemiet pašu elementu kā pasūtītssecība.
- Pāriet uz otro vienumu.
- Salīdziniet to ar pirmo, pamatojoties uz kārtošanas kārtulu.
- Ja nepieciešams, samainiet elementus vietām.
- Ņemiet pirmos divus elementus kā sakārtotu secību.
- Pāriet uz trešo vienumu.
- Salīdzināt ar otro, ja nepieciešams, nomainīt.
- Ja tiek veikta nomaiņa, salīdziniet to ar pirmo.
- Ņemiet trīs elementus kā sakārtotu secību.
Un tā tālāk līdz sākotnējā masīva beigām.
Reālās dzīves ievietošanas kārtošana
Skaidrības labad ir vērts sniegt piemēru, kā šis šķirošanas mehānisms tiek izmantots ikdienā.
Ņemiet, piemēram, maku. Simts, pieci simti un tūkstoš dolāru banknotes guļ nekārtībā banknošu nodalījumā. Tas ir haoss, šādā odziņa ir grūti uzreiz atrast pareizo papīra lapu. Banknošu masīvs ir jāsašķiro.
Pati pirmā ir 1000 rubļu banknote, tūlīt pēc tās - 100. Paņemam simtu un noliekam priekšā. Trešais pēc kārtas ir 500 rubļu, īstā vieta tam ir no simts līdz tūkstotim.
Tādā pašā veidā mēs kārtojam saņemtās kārtis, spēlējot "muļķi", lai būtu vieglāk orientēties.
Operatori un palīgfunkcijas
Ievietošanas kārtošanas metode kā ievadi izmanto sākotnējo sakārtojamo masīvu, salīdzināšanas funkciju un, ja nepieciešams, funkciju, kas nosaka elementu uzskaitīšanas noteikumu. Visbiežāk izmanto tā vietāregulāras cilpas paziņojums.
Pirmais elements pats par sevi ir sakārtota kopa, tāpēc salīdzinājums sākas ar otro.
Algoritms bieži izmanto palīgfunkciju, lai apmainītos ar divām vērtībām (swap). Tas izmanto papildu pagaidu mainīgo, kas patērē atmiņu un nedaudz palēnina kodu.
Alternatīva ir elementu grupas masveida nobīde un pēc tam brīvajā vietā ievietot pašreizējo. Šajā gadījumā pāreja uz nākamo elementu notiek, kad salīdzinājums sniedza pozitīvu rezultātu, kas norāda uz pareizo secību.
Ieviešanas piemēri
Konkrētā ieviešana lielā mērā ir atkarīga no izmantotās programmēšanas valodas, tās sintakses un struktūrām.
Classic C ieviešana, izmantojot pagaidu mainīgo vērtību apmaiņai:
int i, j, temp; for (i=1; i =0; j--) { if (masīvs[j] < temp) pārtraukums; masīvs[j + 1]=masīvs[j]; masīvs[j]=temp; } }
PHP ieviešana:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Šeit vispirms visi elementi, kas neatbilst kārtošanas nosacījumam, tiek pārvietoti pa labi, un pēc tam pašreizējais elements tiek ievietots brīvajā vietā.
Java kods, izmantojot while cilpu:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[iepriekšējā atslēga+1]=arr[iepriekšējaisKey]; arr[iepriekšējaisKey]=currElem; prevKey--; } } }
Koda vispārējā nozīme paliek nemainīga: katrs masīva elements tiek secīgi salīdzināts ar iepriekšējiem un nepieciešamības gadījumā ar tiem apmainīts.
Paredzamais darbības laiks
Acīmredzot labākajā gadījumā algoritma ievade būs jau pareizi sakārtots masīvs. Šādā situācijā algoritmam vienkārši būs jāpārbauda katrs elements, lai pārliecinātos, ka tas atrodas pareizajā vietā, neveicot apmaiņu. Tādējādi darbības laiks būs tieši atkarīgs no sākotnējā masīva garuma O(n).
Sliktākā gadījuma ievade ir masīvs, kas sakārtots apgrieztā secībā. Tam būs nepieciešams liels skaits permutāciju, izpildlaika funkcija būs atkarīga no elementu skaita kvadrātā.
Precīzu permutāciju skaitu pilnīgi nesakārtotam masīvam var aprēķināt, izmantojot formulu:
n(n-1)/2
kur n ir sākotnējā masīva garums. Tādējādi, lai sakārtotu 100 elementus pareizā secībā, būtu nepieciešamas 4950 permutācijas.
Ievietošanas metode ir ļoti efektīva mazu vai daļēji sakārtotu masīvu kārtošanai. Tomēr nav ieteicams to lietot visur, jo aprēķini ir ļoti sarežģīti.
Algoritms tiek izmantots kā palīgierīce daudzās citās sarežģītākās šķirošanas metodēs.
Kārtot vienādas vērtības
Ievietošanas algoritms pieder pie tā sauktajiem stabilajiem veidiem. Tas nozīmē,ka tas neapmaina identiskus elementus, bet saglabā to sākotnējo kārtību. Stabilitātes indekss daudzos gadījumos ir svarīgs pareizai secībai.
Iepriekš minētais ir lielisks vizuāls piemērs ievietošanas kārtošanai dejā.
