Unutrašnje sortiranje – pobitno razdvajanje

Uvod

U računarstvu i informatici algoritam sortiranja je proces preuređivanja elemanata nekog skupa po određenom poretku. Sortiranje skupa podataka je preduslov za njegovo efikasno pretraživanje. Sortiranje je takođe vrlo korisno pri utvrđivanju jednakosti dva skupa podataka.
Za izlazni skup podataka, tj. rezultat sortiranja važi da predstavlja permutaciju ulaznog skupa i da je svaki element izlaznog skupa manji ili jednak prethodnom elementu po odabranom poretku.
Ovo je jedna od osnovnih aktivnosti u algoritmima i programima koji se bave obradom podataka. Zbog toga je vrlo bitno poznavanje ovih algoritama. Ranije procene govore da se čak oko 25% računarskog vremena u okviru raznih aplikacija trošilo na operacije sortiranja.
Zbog važnosti korišćenja ove operacije, razvijene su različite metode sortiranja, od kojih se nijedna ne može proglasiti najboljom jer svaka od njih ima svoje nedostatke i prednosti zavisno od uslova.
Jedna od najbitnijih karakteristika jeste vremenska složenost ovih algoritama koja može, u zavisnosti od broja podataka u različitim uslovima, da se kreće u širokom opsegu, od O(n) do O(n2).
Kod podataka koje sortiramo koristimo, kao i kod pretraživanja, termin ključ K za sadržaj polja na osnovu koga ćemo vršiti sortiranja tog zapisa. Tip ključa mora biti takav da može da sadrži tranzitivne relacione operatore ( <, = ,> ).

Vrste sortitanja

Po mestu gde se nalaze podaci koji se uređuju, postoje dve grupe metoda:

• Unutrašnje sortiranje (koristi se za podatke koji mogu da stanu u operativnu memoriju, obično su u formi niza ili tabele)
• Spoljašnje sortiranje (koristi se za uređivanje podataka koji se nalaze na spoljašnjim memorijama u obliku datoteka)

 
Unutrašnje sortiranje

Unutrašnje sortiranje se primenjuje na skupove podataka čija veličina dozvoljava da se svi podaci istovremeno nalaze u operativnoj memoriji. Najčešće su podaci smešteni u vidu jednog vektora, pa se svakom podatku može direktno pristupiti. Zato se unutrašnje sortiranje često naziva i sortiranjem nizova. Ponekad se niz podataka može predstaviti i ulančanom listom, ali tada podacima mora da se pristupa sekvencijalno, pa je ovakvo sortiranje generalno sporije.
Kako je jedan od zahteva pri sortiranju efikasno korišćenje prostora, sa ovog aspekta poželjni su algoritmi koji vrše sortiranje in situ (na mestu), koristeći prostor gde je smešten neuređeni niz uz još samo konstantan broj dodatnih pomoćnih lokacija nezavisan od broja podataka. Još važniji je kriterijum vremenske složenosti kao pokazatelja performansi ovih metoda. Uobičajeni indikatori performanse metoda unutrašnjeg sortiranja u zavisnosti od broja podataka n koji se sortiraju su:

• broj koraka algoritma da bi se došlo do rešenja,
• broj poređenja ključeva (C),
• broj premeštanja zapisa (M).