Sortirani niz

Sortirani niz
Tip	niz
Godina izuma	1945
Izumitelj	Džon fon Nojman
Vremenska kompleksnost u velikoj O notaciji
Algoritam Prosek Najgori slučaj Prostor O(n) O(n) Pretraga O(log n) O(log n) Umetanje O(n) O(n) Brisanje O(n) O(n)

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. 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 $O(logn)$; 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 $O(n)$ 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 $O(logn)$ vremena. U slučaju kada se briše ili ubacuje na kraj niza, u sortiranom nizu se to izvršava za $O(1)$, dok kod balansiranog stabla treba $O(logn)$.

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.

Primena

Komercijalno računastvo

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.

Proces	Vreme izvršavanja
P1	3
P2	4
P3	1
P4	8
P5	6

Vidi još

• Algoritmi sortiranja
• Binarna pretraga