Postoji nekoliko osnovnih algoritama za rješavanje problema sortiranja niza. Jedan od najpoznatijih među njima je sortiranje umetanjem. Zbog svoje jasnoće i jednostavnosti, ali niske učinkovitosti, ova metoda se uglavnom koristi u nastavi programiranja. Omogućuje vam razumijevanje osnovnih mehanizama sortiranja.
Opis algoritma
Suština algoritma sortiranja umetanjem je da se unutar početnog niza formira pravilno uređen segment. Svaki element se uspoređuje jedan po jedan s provjerenim dijelom i umeće na pravo mjesto. Dakle, nakon ponavljanja kroz sve elemente, oni se redaju ispravnim redoslijedom.
Red odabira elemenata može biti bilo koji, mogu se birati proizvoljno ili prema nekom algoritmu. Najčešće se koristi sekvencijalno nabrajanje od početka niza, gdje se formira uređeni segment.
Početak sortiranja može izgledati ovako:
- Uzmi prvi element niza.
- Budući da ga nema s čime usporediti, uzmite sam element kako je naručenoslijed.
- Idite na drugu stavku.
- Usporedi ga s prvim na temelju pravila sortiranja.
- Ako je potrebno, zamijenite elemente na mjestima.
- Uzmite prva dva elementa kao uređeni niz.
- Idite na treću stavku.
- Usporedite ga s drugim, zamijenite ako je potrebno.
- Ako je zamjena napravljena, usporedite je s prvom.
- Uzmi tri elementa kao uređeni niz.
I tako dalje do kraja izvornog niza.
Umetanje u stvarnom životu sortiranje
Radi jasnoće vrijedi dati primjer kako se ovaj mehanizam razvrstavanja koristi u svakodnevnom životu.
Uzmimo, na primjer, novčanik. Novčanice od sto, pet stotina i tisuću dolara u neredu leže u pretincu za novčanice. Ovo je nered, u takvoj mješini teško je odmah pronaći pravi komad papira. Niz novčanica mora biti razvrstan.
Prva je novčanica od 1000 rubalja, a odmah nakon nje - 100. Uzimamo stotinu i stavljamo je ispred. Treći po redu je 500 rubalja, pravo mjesto za njega je između sto i tisuću.
Na isti način razvrstavamo primljene karte kada igramo "Budalu" kako bismo lakše kretali po njima.
Operatori i pomoćne funkcije
Metoda sortiranja umetanjem uzima kao ulaz početni niz koji se sortira, funkciju usporedbe i, ako je potrebno, funkciju koja određuje pravilo za nabrajanje elemenata. Najčešće se koristi umjesto toganaredba regularne petlje.
Prvi element je sam po sebi uređeni skup, tako da usporedba počinje od drugog.
Algoritam često koristi pomoćnu funkciju za razmjenu dviju vrijednosti (swap). Koristi dodatnu privremenu varijablu, koja troši memoriju i malo usporava kod.
Alternativa je masovni pomak grupe elemenata i zatim umetanje trenutnog u slobodni prostor. U ovom slučaju, prijelaz na sljedeći element događa se kada je usporedba dala pozitivan rezultat, što ukazuje na točan redoslijed.
Primjeri implementacije
Specifična implementacija uvelike ovisi o korištenom programskom jeziku, njegovoj sintaksi i strukturama.
Classic C implementacija pomoću privremene varijable za razmjenu vrijednosti:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; niz [j + 1]=niz [j]; niz [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; } }
Ovdje se prvo svi elementi koji ne odgovaraju uvjetu sortiranja pomiču udesno, a zatim se trenutni element umeće u slobodni prostor.
Java kod pomoću while petlje:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr [prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Opće značenje koda ostaje nepromijenjeno: svaki element niza se uzastopno uspoređuje s prethodnim i zamjenjuje se s njima ako je potrebno.
Procijenjeno vrijeme rada
Očito, u najboljem slučaju, ulaz algoritma će biti niz koji je već uređen na pravi način. U ovoj situaciji, algoritam će jednostavno morati provjeriti svaki element kako bi se uvjerio da je na pravom mjestu bez izmjene. Stoga će vrijeme rada izravno ovisiti o duljini izvornog niza O(n).
Unos u najgorem slučaju je niz sortiran obrnutim redoslijedom. To će zahtijevati veliki broj permutacija, funkcija vremena izvođenja ovisit će o broju elemenata na kvadrat.
Točan broj permutacija za potpuno neuređeni niz može se izračunati pomoću formule:
n(n-1)/2
gdje je n duljina izvornog niza. Dakle, bilo bi potrebno 4950 permutacija da se 100 elemenata rasporedi ispravnim redoslijedom.
Metoda umetanja vrlo je učinkovita za sortiranje malih ili djelomično sortiranih nizova. Međutim, ne preporuča se primjenjivati ga posvuda zbog velike složenosti izračuna.
Algoritam se koristi kao pomoćni u mnogim drugim složenijim metodama sortiranja.
Poređaj jednake vrijednosti
Algoritam umetanja pripada takozvanim stabilnim vrstama. To znači,da ne mijenja identične elemente, već čuva njihov izvorni poredak. Indeks stabilnosti je u mnogim slučajevima važan za ispravno naručivanje.
Gore je izvrstan vizualni primjer sortiranja umetanjem u plesu.
