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 efikasnosti, ova metoda se uglavnom koristi u nastavi programiranja. Omogućava vam da shvatite osnovne mehanizme sortiranja.
Opis algoritma
Suština algoritma sortiranja umetanjem je da se pravilno uređen segment formira unutar početnog niza. Svaki element se poredi jedan po jedan sa provjerenim dijelom i umeće na pravo mjesto. Dakle, nakon ponavljanja kroz sve elemente, oni se redaju u ispravnom redoslijedu.
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.
- Pošto ga nema s čime porediti, uzmite sam element kako je naručenosekvenca.
- Idite na drugu stavku.
- Uporedi sa prvim na osnovu pravila sortiranja.
- Ako je potrebno, zamijenite elemente na mjestima.
- Uzmite prva dva elementa kao uređeni niz.
- Idite na treću stavku.
- Uporedi sa drugim, zameni ako je potrebno.
- Ako je zamjena napravljena, uporedite je sa prvom.
- Uzmi tri elementa kao uređeni niz.
I tako dalje do kraja originalnog niza.
Umetanje u stvarnom životu sortiranje
Radi jasnoće vrijedi dati primjer kako se ovaj mehanizam sortiranja koristi u svakodnevnom životu.
Uzmite, na primjer, novčanik. Novčanice od sto, petsto i hiljadu dolara u neredu leže u odeljku za novčanice. Ovo je nered, u takvoj mešavini teško je odmah pronaći pravi komad papira. Niz novčanica mora biti sortiran.
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 mesto za njega je između sto i hiljadu.
Na isti način sortiramo primljene karte kada igramo "Budalu" kako bismo olakšali navigaciju po njima.
Operatori i pomoćne funkcije
Metoda sortiranja umetanjem uzima kao ulaz početni niz koji se sortira, funkciju poređenja 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 poređenje počinje od drugog.
Algoritam često koristi pomoćnu funkciju za razmjenu dvije vrijednosti (swap). Koristi dodatnu privremenu varijablu, koja troši memoriju i malo usporava kod.
Alternativa je masovno pomicanje grupe elemenata, a zatim umetanje trenutnog u slobodan prostor. U ovom slučaju, prijelaz na sljedeći element se dešava kada je poređenje dalo pozitivan rezultat, što ukazuje na ispravan redoslijed.
Primjeri implementacije
Konkretna implementacija u velikoj mjeri zavisi od programskog jezika koji se koristi, njegove sintakse i strukture.
Classic C implementacija koristeći privremenu varijablu 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; } }
Ovde se prvo svi elementi koji ne odgovaraju uslovu sortiranja pomeraju udesno, a zatim se trenutni element ubacuje u slobodni prostor.
Java kod koristeći while petlju:
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 upoređuje s prethodnim i zamjenjuje s njima ako je potrebno.
Procijenjeno vrijeme rada
Očigledno, 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 zamjene. Dakle, vreme rada će direktno zavisiti od dužine originalnog niza O(n).
Najgori unos je niz sortiran obrnutim redoslijedom. Ovo će zahtijevati veliki broj permutacija, funkcija vremena izvođenja ovisit će o broju elemenata na kvadrat.
Tačan broj permutacija za potpuno neuređeni niz može se izračunati pomoću formule:
n(n-1)/2
gdje je n dužina originalnog niza. Dakle, bilo bi potrebno 4950 permutacija da se rasporedi 100 elemenata u ispravnom redoslijedu.
Metoda umetanja je vrlo efikasna za sortiranje malih ili djelimično sortiranih nizova. Međutim, nije preporučljivo primjenjivati ga svuda zbog velike složenosti proračuna.
Algoritam se koristi kao pomoćni u mnogim drugim složenijim metodama sortiranja.
Poređaj jednake vrijednosti
Algoritam umetanja pripada takozvanim stabilnim sortama. To znači,da ne mijenja identične elemente, već čuva njihov originalni poredak. Indeks stabilnosti je u mnogim slučajevima važan za ispravno naručivanje.
Gore je odličan vizuelni primjer sortiranja umetanjem u plesu.
