SEMINARSKI RAD
Tema:
Unutrašnje sortiranje - pobitno razdvajanje
Predmet:
Algoritmi i strukture podataka
Profesor
:
Student
:
Visoka poslovna škola strukovnih studija, Blace, 2013.
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(n
2
)
.
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)
2
- metodi zamene
- direktna zamena (bubblesort)
- particijsko sortiranje (quicksort)
- pobitno razdvajanje
- metodi spajanja
Pobitno razdvajanje
Razbijanje na particije se pokazalo kao efikasan način sortiranja u prethodnom metodu.
Ovaj princip se koristi i u metodu
pobitnog razdvajanja
(
radix
exchange
). Ovaj metod, za razliku
od svih prethodnih, podrazumeva korišćenje binarne reprezentacije ključa (
radix
= 2) da bi se
donosile binarne odluke u podeli na particije.
Neka binarna reprezentacija ključa ima
m
bitova (
b
m
-1
b
m
-2
....
b
0
)
2
, gde je
b
m
-1
najstariji, a
b
0
najmlađi bit. U prvom koraku se analizira najstariji bit
b
m
-1
i stvaraju se dve particije: gornja u
kojoj su svi ključevi sa
b
m
-1
= 1 i donja u kojoj su svi ključevi sa
b
m
-1
= 0. Zatim se u obe particije
isti postupak ponavlja konsultujući bit
b
m
-2
. Postupak se nastavlja do particija jedinične veličine
ili dok se ne ispitaju svi bitovi.
Postupak razdvajanja se vrši veoma slično kao u
quicksort-
u. Za particiju koja se obrađuje uvedu
se dva tekuća indeksa:
down
koji se na početku postavi na donju granicu particije i
up
na gornju
granicu particije. Zatim se
down
inkrementira sve dok se ne nađe ključ kod koga je tekući bit
odlučivanja 1, a
up
se dekrementira sve dok se ne nađe ključ kod kojeg je taj isti bit 0, pa ova
dva ključa zamene mesta. Ovo se radi sve dok ne postane
down
veće od
up
. Postupak pobitnog
razdvajanja je ilustrovan na slici:
4
