Adaptivno sortiranje

Algoritam za sortiranje spada u grupu adaptivnog sortiranja, ako koristi postojeći poredak na ulazu. Adaptivno sortiranje se uglavnom vrši izmenom postojećih algoritama za sortiranje.

Motivacija

Algoritmi koji su zasnovani na poređenjima su tradicionalno težili ostvarivanju vremensku složenost O(n). Adaptivno sortiranje ima prednost u tome sto već postoji red u ulazu, tako da može da postigne i bolju složenost. Prema tome vreme za sortiranje je funkcija koja polako raste sa povećanjem niza i "nereda" u njemu. Drugim rečima, što je niz više sortiran pri unosu, to je algoritam brži.

Ovo je zanimljiv algoritam, jer se nizovi koji su već uređeni često sreću u praksi. Učinak postojećih algoritama za sortiranje može biti dokazan uzimajući u obzir presortiranost niza.

Primetite da većina algoritama koji imaju najbolju vremensku složenost procenjenu na najgorem slučaju, posebno hipsort i mergesort, ne uzimaju u obzir prethodnu uređenost ulaznog niza, iako je ovaj nedostatak lako primetiti, naročito kod mergesort-a proverom da li je levi element manji ili jednak od prvog desnog. U tom slučaju mergesort može biti zamenjen jednostavnom konkatenacijom- modifikacijom koja je dobra u slučaju pravljenja prilagodljivog sortiranja.

Primeri

Klasičan primer adaptivnog sortiranja je sortiranje umetanjem. U ovom algoritmu prolazimo kroz niz s leva na desno i tražimo poziciju za trenutni element i umećemo ga u prethodno sortirani niz. Pseudokod ovog algoritma izgleda ovako:

 procedure Straight Insertion Sort (X, n):
 X[0] := − ∞;
 for j := 2 to n do
 begin i := j − 1;
      t := X[j];
      while t < X[i] do
      begin X[i + 1] := X[i];
            i := i - 1
      end;
      X[i + 1] := t;
 end;

Performanse ovog algoritma mogu biti opisane brojem inverzija ulaza. Onda će T(n) biti I(A)+ (n-1), gde je I(A) broj inverzija. Koristeći ove mere preuređenosti-koje su u vezi sa brojem inverzija-sortiranje umetanjem brže sortira uređeni niz. Drugi primeri adaptivnog sortiranja su prilagodljivo hip sortiranje i adaptivno sortiranje spajanjem. Dijkstrin Smutsort je takođe varijacija hipsorta koja podrazumeva korišćenje algoritma adaprivnog sortiranja.

Timsort koji se koristi kao genetički algoritam za sortiranje za više programskih jezika, npr. Pajton, takođe je adaptivni.

Literatura

Hagerup, Torben; Katjainen, Jyrki (2004). Algorithm Theory – SWAT 2004. Berlin Heidelberg: Springer-Verlag. стр. 221—222. ISBN 978-3-540-22339-9.
Mehta, Dinesh P.; Sahni, Sartaj (2005). Data Structures and Applications. USA: Chapman & Hall/CRC. стр. 11‑8—11‑9. ISBN 978-1-58488-435-4.
Estivill-Castro, Vladmir; Derick Wood (1992). „A survey of adaptive sorting algorithms”. ACM. New York, NY, USA: ACM. 24 (4): 441—476. ISSN 0360-0300. doi:10.1145/146370.146381.
Petersson, Ola; Alistair Moffat (1992). „A framework for adaptive sorting”. Lecture Notes in Computer Science. Berlin: Springer Berlin / Heidelberg. 621: 422—433. ISSN 1611-3349. doi:10.1007/3-540-55706-7_38. Приступљено 23. 02. 2009. ^{[мртва веза]}

Vidi još