Sortiranje

Sortiranje je proces izlaganja elemenata kolekcije u određenom redosledu prema ključu ili kriterijumu. U užem smislu, u računarstvu se podrazumeva niz algoritama koji rearraniraju podatke tako da su elementi uredno poređani, najčešće po rastućem ili opadajućem redosledu. Primena sortiranja obuhvata olakšavanje pretraživanja, poravnavanje podataka, poravnanje rezultata u izveštajima i optimizaciju drugih operacija koje zavise od redosleda.

Sortiranje se deli na dve velike kategorije: sortiranje zasnovano na poređenju i sortiranje koje ne koristi poređenje. Kod sortiranja zasnovanog na poređenju, algoritmi omogućavaju poređenje parova elemenata i orga nizaciju na osnovu rezultata tih poređenja. Za ove algoritme postoji teoretski donji okvir složenosti od O(n log n) u proseku, uz potencijalno lošije scenarije (n log n ili više), zavisno od algoritma. Kod ne poređenja, koriste se tehničke strategie poput brojanja, radik sort-a ili bucket sort-a i mogu postići bolje od O(n log n) složenosti za specifične tipove podataka.

Važne osobine uključuju stabilnost (da li sortiranje čuva relativni red ekvivalentnih elemenata), in-place karakter (potreba za dodatnim prostorom) i podršku za eksterno sortiranje (kada podaci ne stanu u memoriju). U praksi, sortiranje se koristi u bazama podataka za ORDER BY operacije, u prenosu podataka, analizi i pripremi skupova podataka za dalju obradu.

Najčešći primeri algoritama su quicksort, mergesort, heapsort, insertionsort, bubble sort, kao i ne-poređenja sortovi poput counting sort, radix sort i bucket sort. U mnogim realnim sistemima često se kombinuju ili prilagođavaju (npr. timsort).