Obstaja več osnovnih algoritmov za reševanje problema razvrščanja matrike. Eden najbolj znanih med njimi je sortiranje z vstavljanjem. Zaradi svoje jasnosti in preprostosti, a nizke učinkovitosti, se ta metoda uporablja predvsem pri poučevanju programiranja. Omogoča vam razumevanje osnovnih mehanizmov razvrščanja.
Opis algoritma
Bistvo algoritma razvrščanja z vstavljanjem je, da se znotraj začetnega niza oblikuje pravilno urejen segment. Vsak element se enega za drugim primerja s preverjenim delom in vstavi na pravo mesto. Tako se po iteraciji po vseh elementih razvrstijo v pravilnem vrstnem redu.
Vrstni red izbire elementov je lahko poljuben, lahko jih izberemo poljubno ali po nekem algoritmu. Najpogosteje se uporablja zaporedno štetje od začetka matrike, kjer se oblikuje urejen segment.
Začetek razvrščanja bi lahko izgledal takole:
- Vzemite prvi element matrike.
- Ker ga ni s čim primerjati, vzemite sam element kot naročenozaporedje.
- Pojdi na drugi element.
- Primerjaj ga s prvim na podlagi pravila razvrščanja.
- Po potrebi zamenjajte elemente na mestih.
- Prva dva elementa vzemite kot urejeno zaporedje.
- Pojdi na tretji element.
- Primerjaj ga z drugim, po potrebi zamenjaj.
- Če je opravljena zamenjava, jo primerjajte s prvo.
- Vzemite tri elemente kot urejeno zaporedje.
In tako naprej do konca prvotnega niza.
Razvrstitev vstavljanja v resničnem življenju
Za jasnost je vredno navesti primer, kako se ta mehanizem razvrščanja uporablja v vsakdanjem življenju.
Vzemite na primer denarnico. Bankovci po sto, petsto in tisoč dolarjev ležijo v neredu v predelu za bankovce. To je nered, v takšni mešanici je težko takoj najti pravi kos papirja. Niz bankovcev mora biti razvrščen.
Prvi je bankovec za 1000 rubljev, takoj za njim pa - 100. Vzamemo sto in ga položimo spredaj. Tretji po vrsti je 500 rubljev, pravo mesto zanj je med sto in tisoč.
Na enak način razvrstimo prejete karte, ko igramo "Norec", da olajšamo krmarjenje po njih.
Operatorji in pomožne funkcije
Metoda razvrščanja z vstavljanjem vzame kot vhod začetno matriko, ki jo je treba razvrstiti, primerjalno funkcijo in, če je potrebno, funkcijo, ki določa pravilo za naštevanje elementov. Najpogosteje se uporablja namesto tegastavek navadne zanke.
Prvi element je sam po sebi urejen niz, zato se primerjava začne od drugega.
Algoritem pogosto uporablja pomožno funkcijo za izmenjavo dveh vrednosti (swap). Uporablja dodatno začasno spremenljivko, ki porabi pomnilnik in nekoliko upočasni kodo.
Alternativa je, da množično premaknete skupino elementov in nato vstavite trenutnega v prosti prostor. V tem primeru pride do prehoda na naslednji element, ko je primerjava dala pozitiven rezultat, kar kaže na pravilen vrstni red.
Primeri implementacije
Posebna izvedba je v veliki meri odvisna od uporabljenega programskega jezika, njegove sintakse in strukture.
Izvedba klasične C z uporabo začasne spremenljivke za izmenjavo vrednosti:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; matrika [j + 1]=matrika [j]; array[j]=temp; } }
PHP Implementacija:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Tukaj se najprej vsi elementi, ki se ne ujemajo s pogojem razvrščanja, premaknejo v desno, nato pa se trenutni element vstavi v prosti prostor.
Java koda z uporabo while zanke:
javno statično void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr [prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Splošni pomen kode ostaja nespremenjen: vsak element matrike se zaporedno primerja s prejšnjimi in po potrebi zamenja z njimi.
Predvideni čas delovanja
Očitno bo v najboljšem primeru vhod algoritma matrika, ki je že urejena na pravi način. V tej situaciji bo moral algoritem preprosto preveriti vsak element, da se prepriča, ali je na pravem mestu, ne da bi izvajal izmenjave. Tako bo čas delovanja neposredno odvisen od dolžine prvotnega niza O(n).
Najslabši vnos je matrika, razvrščena v obratnem vrstnem redu. To bo zahtevalo veliko število permutacij, funkcija izvajanja bo odvisna od števila elementov na kvadrat.
Natančno število permutacij za popolnoma neurejeno matriko je mogoče izračunati s formulo:
n(n-1)/2
kjer je n dolžina izvirnega niza. Tako bi bilo potrebnih 4950 permutacij, da bi razporedili 100 elementov v pravilnem vrstnem redu.
Metoda vstavljanja je zelo učinkovita za razvrščanje majhnih ali delno razvrščenih nizov. Vendar ga ni priporočljivo uporabljati povsod zaradi visoke zapletenosti izračunov.
Algoritem se uporablja kot pomožni pri mnogih drugih bolj zapletenih metodah razvrščanja.
Razvrsti enake vrednosti
Algoritem vstavljanja spada v tako imenovane stabilne vrste. To pomeni,da ne zamenja enakih elementov, ampak ohranja njihov prvotni vrstni red. Indeks stabilnosti je v mnogih primerih pomemben za pravilno naročanje.
Zgoraj je odličen vizualni primer razvrščanja vstavljanja v plesu.
