Пређи на садржај

Sortirani niz

С Википедије, слободне енциклопедије
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)

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.

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.

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.

Džon fon Nojman je napisao prvi program za sortiranje (sortiranje spajanjem) 1945. godine, za vreme pravljenja EDVAC računara.[2]

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
  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.