Spoljašnje sortiranje, vrste i njihova efikasnost

Uvod:

Pod sortiranjem se podrazumeva razmeštanje elemenata nekog skupa u neopadajući ili nerastući poredak. Skup može biti predstavljen nizom, listom, datotekom, itd. Ako se sortira skup elementarnih podataka (brojeva, stringova), onda se sortiranje vrši upravo po vrednosti tih podataka. Moguće je sortiranje primeniti i na strukture kao elemente, pri čemu se sortiranje vrši prema nekom (zadatom) članu strukture, tj. po vrednosti tog člana koji se onda naziva članom sortiranja.
Razlozi za sortiranje su višestruki, npr.:

1. rešavanje zadataka grupisanja tj. sakupljanja elemenata sa jednakom vrednošću (ili jednakom vrednošću zadatog polja);
2. nalaženje zajedničkih elemenata (preseka) dva ili više skupova (npr. datoteka); za sortirane skupove ovaj zadatak je jednostavan i obavlja se u jednom prolazu kroz svaki od skupova;
3. pretraživanje – nalaženje elementa sa zadatom vrednošću (zadatog polja), za skup sortiran po vrednostima tog polja obavlja se lako (npr. traženje po rečniku moguće je upravo zahvaljujući njegovoj sortiranosti).Postoje dve vrste sortiranja – unutrašnje i spoljašnje sortiranje, i dve grupe metoda koje se na njih odnose, svaka metoda praćena nizom algoritama za njenu implementaciju.

Spoljašnje sortiranje

Termin spoljašnje sortiranje se koristi za uređivanje skupa podataka koji se zbog veličine ne može odjednom smestiti u operativnu memoriju, već se nalazi na spoljašnjim medijumima.
Algoritmi unutrašnjeg sortiranja su optimizovani u odnosu na cene operacija sa operativnom memorijom, a kako su karakteristike pristupa spoljašnjim memorijskim uređajima potpuno različite, ovi algoritmi su, u opštem slučaju, neprimenjivi za spoljašnje sortiranje, iako je problem sortiranja semantički isti.
S obzirom na to da su podaci koji se uređuju smešteni u datotekama, spoljašnje sortiranje se, ponekad, naziva i sortiranje datoteka.
Kod nizova u operativnoj memoriji, pristup svakom elementu u svakom trenutku je ravnopravno moguć sa istom cenom. Međutim, kod datoteka (pogotovo sekvencijalnih) pristup podacima je značajno ograničen što se neminivno odražava i na algoritme sortiranja.
Sami eksterni uređaji se veoma razlikuju po načinu smeštanja podataka, ceni pristupa i ograničenjima koja nameću pri pristupu, što mnogo zavisi i od tehnoloških parametara. Prema tome, algoritmi treba da u implementaciji budu prilagođeni i samom uređaju.
Osnovni postupak spoljašnjeg sortiranja se može prikazati na jednom hipotetičkom primeru. Neka datoteka koju treba sortirati sadrži 2000 zapisa, a neka u operativnu memoriju može da stane samo 1000 zapisa.
Tada se zapisi 1 … 1000 mogu učitati u operativnu memoriju, sortirati pogodnom metodom unutrašnjeg sortiranja, pa se sortirana sekvenca zapisa upiše u pomoćnu datoteku. Za ovakve sortirane sekvence zapisa u okviru datoteke uobičajeno se koristi naziv ran.
Zatim se, na isti način sortiraju zapisi 1001 … 2000 i dobije drugi ran koji se smešte u drugu pomoćnu datoteku.
Na kraju se primenjuje metod spajanja kojim se od dve pomoćne datoteke dobija konačna sortirana datoteka, pa se ona upisuje na odredišni uređaj.