Sortiranje

Sortiranje je proces preuređenja datog skupa objekata po određenom kriterijumu. Ono kasnije olakšava pretraživanje datog skupa. To je jedna od najvažnijih aktivnosti u obrađivanju podataka. Sortiranje je dobro izučena oblast i postoji više lepih primera u kojima se vidi raznovrsnost algoritama. Sortiranje se primenjuje prilikom sortiranja imena u telefonskom imeniku, pojmova u nekoj knjizi, reči u rečniku ili robe u nekom magacinu.

 

Algoritmi sortiranja

Najčešće korišćeni algoritmi su:

  1. sortiranje umetanjem
  2. sortiranje selekcijom
  3. sortiranje zamenom

 

Sortiranje umetanjem

Primer za sortiranje umetanjem je slaganje karata u špilu:

dva niza:

  • odredišni (sortiran) a1, ... ai-1
  • i izvorni (nesortiran) ai, ...an

 


Slika 1. algoritam sortiranja umetanjem

U svakom koraku, počevši od i=2, uzima se i-ti element iz izvornog niza i prebacuje u odredišni niz umetanjem na određeno mesto, tako da odredišni niz bude uređen po izabranom kriterijumu.

Na slici 2 vidimo da iz crvenog niza biramo član niza na mestu i, i ubacujemo ga na traženo mesto u plavom nizu. Prvi korak počinje od i=2 i u ovom slučaju ostaje na svom prethodnom mestu. U koraku i=3 član 12 ide na početak. U koraku i=4 član 42 ide na mesto 2 i tako dalje.
 

Slika 2. primer sortiranja umetanjem

 

Sortiranje selekcijom

Pronalazi se najmanji element datog niza. On se stavlja na prvu poziciju niza koji će biti sortiran. Među preostalim članovima se traži sledeći najmanji element i on se stavlja na drugu poziciju. Postupak se ponavlja sve dok se niz ne sortira. Na slici 4 je prikazan primer sortiranja selekcijom.

 

Slika 3. algoritam sortiranja selekcijom

 

Slika 4. sortiranje niza selekcijom

 

Vidimo da je u prvom prolazu nađen broj 6 kao najmanji. On se stavlja na prvo mesto. U sledećoj iteraciji je među preostalim članovima niza pronađen broj 12 i on ide na drugo mesto. Postupak se nastavlja dok se ceo niz ne sortira.

 

Sortiranje zamenom mesta (bubble sort)

Algoritam se bazira na poređenju susednih elemenata i njihovoj zameni u slučaju da je manja vrednost smeštena posle veće vrednosti. Sve dok se niz ne sortira u potpunosti, algoritam svaki put prolazi kroz ceo niz, što je veoma neefikasno.


 


slika 5. bubble sort algoritam

 

Naziv bubble-sort (mehurići) ovog metoda potiče od toga što prilikom sortiranja manji članovi „isplivavaju" na početak niza, što se vidi na sledećoj slici.

 

Slika 6. Primer metoda zamene

Članovi 18 i 6 su u pogrešnom redosledu, te im se zamenjuju mesta. Zatim su 94 i 6 pogrešno poređani, pa se i njima zamenjuju mesta. Ponavljajući postupak, broj 6 izlazi na vrh niza. To smo izveli u 6 koraka. Za sledeću iteraciju, i=2, imamo par 55 i 12, kao i par 94 i 18, koji su loše poređani. Istovremenim zamenama, 12 i 18 isplivavaju polako na vrh. Ceo postupak se dalje ponavlja.

Dodaj komentar Sviđa mi se - (0) Ne sviđa mi se - (0)    

  • Algoritmi sortiranja 1
  • Algoritmi sortiranja 2
  • Algoritmi sortiranja 3
  • Algoritmi sortiranja 4
  • Algoritmi sortiranja 5