Sortiranje

Vrsta sortiranja

Sortiranje je bilo koji sistematični proces uređivanja, i ima 2 zajednička, a ipak različita značenja:

1. Uređivanje (sortiranje): uređivanje stavki jednu za drugom po nekom kriterijumu;
2. Kategorizacija: grupisanje stavki sa sličnim osobinama;

Sortiranje informacija ili podataka

U informatici, proces uređivanje stavki jednu za drugom se naziva "sortiranje". Sortiranje je česta operacija u mnogim aplikacijama, i postoji mnogo efikasnih algoritama koji su baš zbog toga izmišljeni.

Najčešće primene sortiranja su u:

• poboljšanju efikasnosti alogoritama pretrage;
• poboljšanju efikasnosti za spajanje nizova.

Glavni cilj sortiranja informacija je da optimizzje svoju korisnost za specifične zadatke. Uopšteno, postoje dva načina grupisanja informacija: po kategoriji npr. katalog za kupovinu gde su stavke zajedno grupisane pod nazivom kao što je 'kuća', 'sport i slobodno vreme', 'ženska odeća' itd. i po intenzitetu nečega, kao što je cena , npr. najjeftinije do najskuplje stvari (uobičajena skala). Richard Saul Wurman, je u svojoj knjizi Information Anxiety, predlaže da najčešća sortiranju su po imenu, po lokaciji i po vremenu (ovo su zapravo posebni slučajevi kategorije i hijerarhije). Oni zajedno daju skraćenicu LAVKH (Lokacija, Alfabet, Vreme, Kategorija, Hijerarhija) i mogu se koristiti da opišu svaki tip sortiranja informacija.

Često su informacije sortirane različitim metodama na različitim nivoima apstrakcije: npr. telefoni u Engleskom adresatu koji su sortirani po lokaciji, po kategoriji (poslovni ili stambeni) i zatim po alfabetu. Savremena medija i dalje se slaže sa ovim osnovnim metodama sortiranja: npr. Gugl pretraga vraća listu veb stranica u hijerarhijskoj listi zasnovanoj po njihovom ličnom sistemu bodovanja, tj koliko su blizu zadatom uslovu (od najbližeg do najdaljeg).

Suprotno od sortiranja je preuređenje niza stavki po slučajnoj ili određenoj stvari, i zove mešanje.

Sortiranje n-torki (zavisi od značenje tj. evidencije sa poljima) se može uraditi na osnovu jedne ili više stvari (komponente). Stvari mogu biti sortirane na osnovu svojih osobina. Takva komponenta-osobina se zove ključ sortiranja.

Na primer, stavke su neke knjige, ključ sortiranja su naslovi, autor, i uređenje je po alfabetu.

Novi ključ sortiranja se može napraviti od dva ili više ključeva po leksikografijskom uređenju. Prvi se zove primarni ključ sortiranja, a drugi sekundarni ključ sortiranja, itd.

Na primer, adrese se mogu sortirati prema gradovima kao primarni ključ, i prema ulicama kao sekundarni ključ.

Ako je vrednost ključa skroz uređena , ključ definiše slabo uređenje stavki: stvari sa istim ključom sortiranja su jednake prema sortiranju. Ako različite stvari imaju imaju rezličite vrednosti ključeva onda to predstavlja jedinstveno uređenje svari.

Radnici sortiraju pošiljke u pošti

Standardno uređenje se često naziva rastuće (odgovara na činjenicu da je standardni poredak brojeva rastući, odnosno od A do Z-Š, od 0 do 9), obrnutim redosledom opadajuće (Š-Z do A, 9 do 0). Za datume i vremena, rastući poredak znači da ranija vrednost prethodi kasnijoj, npr 1.1.2000 će biti ispred 1/1/2001.

Nekoliko poznatih algoritama u informatici

• Sortiranje mehurom : Zameni mesta dva susedna elementa, ako nisu uređena. Ponavljaj sve dok niz ne bude sortiran.
• Sortiranje umetanjem : Skenira uzastopne elemente koji nisu uređeni, onda ih ubacuje na odgovarajuće mesto.
• Sortiranje selekcijom : Traži najmanji element u nizu, i stavlja ga na odgovarajuće mesto. Zameni ga sa vrednošću na prvoj poziciji. Ponavlja sve dok niz ne bude sortiran.
• Kviksort : Deli niz u dva dela. U prvom delu, svi elementi su manji i jednaki od vrednosti pivota. U drugom delu, svi elementi su veći ili jednaki od vrednosti pivota. Na kraju, sortira oba dela rekurzivno.
• Sortiranje spajanjem : Deli listu elemenata na dva dela, sortira ih pojedinačno i zatim ih spaja.

Fizički procesi sortiranja

Klasifikacija železničke pruge, koristi se za sortiranje teretnih vagona

U industrijskim procesim se znatno koristi sortiranje za različite procese. Na primer, prilikom eksploatacije zlata iz ruda, mašine koriste gravitaciju, vibraciju i imaju kanale kojim se razdvaja zlato od ostalih materija (sortirajući po veličini i težini). Sortiranje je takođe prirodni proces koji dovodi do koncentracije rude ili sedimenta. Rezultati sortiranja aplikacije, na osnovu nekog uslova, dele ga na njegove komponenate zasnovane na promenljivom kvalitetu. Materijale koji su različiti, ali veoma malo, kao što su izotopi uranijuma, je veoma teško razdvojiti.

Optičko sortiranje je automatski proces sortiranja čvrstih proizvoda pomoću kamere i/ili lasera, i ima široku primenu u prehrambenoj industriji.

Vidi još

• Algoritmi za sortiranje
• Unikodni algoritam upoređivanja
• Organizacija

Spoljašnje veze

• Demonstration of Sorting Algorithms (uključujući sortiranje mehurom i kviksort)
• Animated video objašnjenje sortiranja mehurom i kviksorta i razlike u performansama.