Ciklično sortiranje — разлика између измена

м
Разне исправке; козметичке измене
Нема описа измене
м (Разне исправке; козметичке измене)
| širina slike=250
| struktura=[[Niz]]
| namena=[[Алгоритми_сортирањаАлгоритми сортирања|sortiranje]]
| vkompleksnost= ''-{[[Велико_OВелико O|O]](n²)}-''
| mkompleksnost=-{[[Велико_OВелико O|O]](n)}-''
| stabilan=ne
}}
'''Ciklično sortiranje''' predstavlja nestabilni, in-place [[algoritam]] za sortiranje, pripada grupi [[Алгоритми_сортирањаАлгоритми сортирања#Алгоритми сортирања поређењем|sortiranja poredjenjem]] i optimalan je u smislu ukupnog broja upisivanja u niz. Zasniva se na ideji da se [[permutacija]] koju treba sortirati može podeliti na cikluse. Zatim rotiramo cikluse da bi dobili sortiran niz. Vremenska složenost algoritma je [[Велико_ОВелико О|O]](n²).
 
Za razliku od skoro svakog drugog sortiranja, ovde se elementi nikada ne upisuju negde u nizu samo da bi bili sklonjeni sa puta. Svaka vrednost je upisana ili nula puta, ako je već na svom mestu, ili tačno jednom, na svoju poziciju. Ovim se postiže minimalan broj upisivanja za kompletno in-place sortiranje.
Minimizacija broja pisanja veoma je korisna kada je zapisivanje podataka skupo, npr na [[EEPROM]]-u ili [[Флеш_меморијаФлеш меморија|fleš memoriji]] gde svako zapisivanje smanjuje životni vek memorije.
 
== Algoritam ==
</source>
 
== Specijalni slučejevi ==
Kada niz sadrži samo ponovljene vrednosti iz relativno malog opsega brojeva, može se napraviti savršena [[Хеш_табелаХеш табела|heš funkcija]] [[Константно_времеКонстантно време|konstantnog vremena]] koja značajno ubrzava pronalaženje mesta na koje treba postaviti element, podižući efikasnost sa [[Велико_ОВелико О|O]](-{n}-²) na [[Велико_ОВелико О|O]](-{n+k}-) gde je -{k}- broj adresa heš tabele. Na kraju je niz sortiran po redosledu heširanja, pa je važno izabrati dobru heš funkciju koja će niz sortirati na potreban način.
 
Pre sortiranja treba napraviti [[histogram]], koji će beležiti broj pojavljivanja svakog heša u nizu. Zatim napraviti tabelu koja će sadržati kumulativne sume svakog ulaza histograma. Ta tabela će sadržati poziciju svakog elementa u nizu. Zatim se pravo mesto svakog elementa može pronaći heširanjem (u [[Константно_времеКонстантно време|konstantnom vremenu]]) i pomoću tabele, umesto linearnom pretragom.
 
<!--== Reference ==
-->
== Literatura ==
* {{cite journal |
| last=Musser |
| first=David |
| title=Introspective Sorting and Selection Algorithms |
| url=http://www.cs.rpi.edu/~musser/gp/introsort.ps |
| doi=10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# |
| journal=Software: Practice and Experience |
| volume=27 |
| issue=8 |
| publisher=Wiley |
| year=1997 |
| pages=983–993}}
* -{Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.}-
 
1.572.075

измена