Википедија

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

Интерактиван преглед историје
Новија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нова страница: == Algorithm == The following algorithm finds cycles and rotates them, giving a sorted result. Note that '''range(''a'', ''b'')''' goes from '''''a''''' to '''''b…
 
Нема описа измене
Ред 1:
[[File:Cyclesort.png|thimb|Ciklično sortiranje]]
 
Ciklicno sortiranje predstavlja nestabilni, in-place [[algoritam]] za sortiranje, pripada grupi [[Алгоритми_сортирања#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B8_.D1.81.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.B0.D1.9A.D0.B0_.D0.BF.D0.BE.D1.80.D0.B5.D1.92.D0.B5.D1.9A.D0.B5.D0.BC|sortiranja poredjenjem]] i teoretski je optimalan u smislu ukupnog broja upisivanja u originalan niz. Zasniva se na ideji da se [[permutacija]] koju treba sortirati može podeli 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 pisanja za kompletno in-place sortiranje.
== Algorithm ==
Minimizacija broja pisanja veoma je korisna kada je zapisanje podataka skupo, npr na [[EEPROM]]-u ili [[Флеш_меморија|fleš memoriji]] gde svako zapisivanje smanjuje životni vek memorije.
The following [[algorithm]] finds cycles and rotates them, giving a sorted result. Note that '''range(''a'', ''b'')''' goes from '''''a''''' to '''''b'' ‑ 1'''.
 
== Algoritam ==
Ovaj [[algoritam]] pronalazi cikluse i rotira ih, i na kraju daje sortiran rezultat. '''Napomena:''' Opseg (a,b) sadrži brojeve od a do b-1.
<source lang="python">
# Sort an array in place and return the number of writes.
Линија 45 ⟶ 50:
return writes
</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.
 
 
== External links ==
Преузето из „https://sr.wikipedia.org/wiki/Ciklično_sortiranje”