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.

Sortirani niz
Tipniz
Godina izuma1945
IzumiteljDž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)

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.

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

Vidi još уреди

Reference уреди

  1. ^ „Sorting Algorithms”. GeeksforGeeks (на језику: енглески). Приступљено 9. 4. 2020. 
  2. ^ Knuth, Donald Ervin (1997). The art of computer programming. Addison-Wesley. ISBN 0-201-89685-0. OCLC 951274350. 
  3. ^ „Sorting Applications”. algs4.cs.princeton.edu. Приступљено 9. 4. 2020.