Sortirani niz
Sortirani niz | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tip | niz | ||||||||||||||||||||
Godina izuma | 1945 | ||||||||||||||||||||
Izumitelj | Džon fon Nojman | ||||||||||||||||||||
Vremenska kompleksnost u velikoj O notaciji | |||||||||||||||||||||
|
Sortirani niz je niz u kojem je svaki element sortiran u brojevnom, slovnom ili nekom drugom redu, i pozicioniran u proračunatoj memoriji na računaru. Najčešće se koriste u računarima da se impementiraju statične tabele sa različitim vrednostima koje imaju isti tip. Sortiranje niza je korisno za organizovanje podataka u određenoj formi i da im se brzo pristupa.
Metode
Postoji mnogo poznatih metoda pomoću kojih niz moze biti sortiran selekcijom, mehurom, umetanjem, spajanjem, prebrojavanjem, kviksortom i hipsortom.[1] Ove tehnike sortiranja imaju različite algoritme i takođe postoje različite prednosti za korišćenje nekog od njih.
Pregled
Sortirani nizovi su prostorno najštedljivija struktura podataka.
Elementi koji su sortirani, binarnom pretragom se pretražuju kompleksnošću ; tako sortirani nizovu su pogodni kada elementi treba brzo da se nađu. Ova kompleksnost je ista kao i kod samobalansirajućih binarnih stabala pretrage.
U nekim strukturama podataka koristi se niz objekata. U takvim slučajevima, iste metode sortiranja mogu da se koriste za sortiranje struktura u odnosu na neki ključ, na primer, sortiranje studenata po brojevima, imenima ili ocenama.
Ako je u pitanju dinamičko sortiranje, onda je moguće brisanje i ubacivanje elemenata. Brisanje i ubacivanje elemenata zahteva vremena, zato što mora da se prođe kroz sve elemente, u poređenju sa samobalansirajućim stablom, gde za brisanje i ubacivanje elemenata treba vremena. U slučaju kada se briše ili ubacuje na kraj niza, u sortiranom nizu se to izvršava za , dok kod balansiranog stabla treba .
Elementi u sortiranom nizu mogu da se pretražuju preko indeksa u O(1) vremenu, za druge kompleksnije operacije potrebno je O(log n) ili O(n) vremena.
Istorija
Džon fon Nojman je napisao prvi program za sortiranje (sortiranje spajanjem) 1945. godine, za vreme pravljenja EDVAC računara.[2]
Primena
Komercijalno računastvo[3]
Vladine organizacije, privatne kompanije i aplikacije bazirane na vebu imaju mnogo podataka. Podacima se često pristupa više puta. Čuvanje podataka kao soriran niz omogućuje lak pristup podacima.
Diskretna matematika
Soritani nizovi mogu da se koriste za implementaciju Dajkistrinog algoritma ili Primovog algoritma. Takođe i za algoritme kao što je Kruskalov za traženje minimalnih razapinjućih stabala.
Prioritetna zakazivanja
Kod operativnih sistema, mnogi procesi čekaju na izvršavanje, jer procesor može da obrađuje samo jedan proces u određenom trenutku. Procesi se šalju procesoru po prioritetu zasnovanom na sortiranom nizu.
Raspoređivanje po vremenu izvršavanja
Ovo je poseban slučaj prioritetnog zakazivanja. Procesi se sortiraju na osnovu vremena trajanja. Proces koji zahteva najmanje vremena će se izvršiti prvi.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Priority_scheduling.pdf/page1-300px-Priority_scheduling.pdf.jpg)
Proces | Vreme izvršavanja |
---|---|
P1 | 3 |
P2 | 4 |
P3 | 1 |
P4 | 8 |
P5 | 6 |