Sortiranje podelom — разлика између измена
Садржај обрисан Садржај додат
м Renamed template |
м sablon cinjenica; козметичке измене |
||
Ред 1:
'''Sortiranje (razvrstavanje) podelom''' ({{jez-eng-lat|Unshuffle sort}}) je [[Алгоритми сортирања|algoritam sortiranja]].
== Uvod ==
-{''UnShuffle sort''}- je sortiranje podelom ili sortiranje objedinjavanjem koje je razvijeno od strane Art S. Kagela. -{''UnShuffle''}- je najefikasniji kada se sortiraju podaci koji imaju malu entropiju, u smislu da se podaci dobro uređeni ili sadrže dobro uređene pod-sekvence. Trenutna implementacija je rezultat višegodišnjeg eksperimentiranja. Sortiranje uključuje dvije faze. Tokom prve faza podele predmeti se raspoređuju u promjenjivom broju uređenih listi korišćenjem strukture koja smanjuje broj poređenja. Nakon što su svi predmeti raspoređeni, sortirane liste se objedinjuju u jednu iylaynu listu. UnShuffle je jedan od retkih sortova koje se mogu direktno primeniti na povezane liste.
Algoritam koristi strukturu podataka pod nazivom 'stub' ({{jez-eng-lat|pile}}) koja je uređeni red u kome dozvoljeno ubacivanje elemenata na početku liste, ukoliko je novi element manji ili jednak trenutnoj glavi ili na kraju liste, ako je novi element veća ili jednak repu liste. Nije dozvoljeno umetanje elemenata između postojećih elemenata. To se obično sprovodi korišćenjem dvostruko povezane liste
Najbolji slučaj za UnShuffle u slučaju potpuno uređenih ili obrnuto urđenih nizova podataka sa samo jednim stubom korištenjem n-1 poređenja (s preporučenom optimizaciju) i bez objedinjavanja. Nema najgoreg slučaja i može se pokazati da nema niza čija je složenost vaća od O ((K / 4) * N) za fazu I + O (N * (log K)) za fazu II pomoću korišćenjem idealnog objedinjavanja ya fazu II, gdje je K broj stubova kreiranim tokom faze raspoređivanja (faza I).
Budući da sortira povezane liste, a ne nizove podataka samo se pokayivači premeštaju i zbog strukture
stuba ne postoje skupe zamene, tako da vreme sortiranja zavisi od veličine podatka i složenosti ključa.
== Faza I - Faza podele ==
# Uzmi prvi element i kreiraj stub #1 sa elementom#1 kao glavu i rep.
# Ako nema više elementa pređi na fazu II.
# Uzmi sledeći element.
# Odaberite posljednji stub za poređenje.
# Uporedi sa vrhom stuba.
# Ako jednak stvi na vrh stuba, pređi na korak 2.
# Ako je manji, a to nije prvi stub označi prethodni stub i pređi na korak 5.
# Ako je manje i to jeste prvi stub, stavi element na vrh stuba i pređi na korak 2.
# Ako je veći, a to nije posljednji stub stavi na vrh sledećeg stuba (koji je prethodni upoređen), pređi na korak 2, u suprotnom element je veći od kraja stuba.
# Uporedi sa krajem trenutnog stuba.
# Ako jednak stavi na kraj stuba, pređi na korak 2.
# Ako je veći, a to nije prvi stub oynači prethodni stub, pređi na korak 10.
# Ako je manji i to je posljednji stub kreiraj novi stub od elementa i dodati u listu stubova, pređi na korak 2.
# Ubaci na kraj sledećeg stuba, pređi na korak 2.
== Faza II – Faza objedinjavanja ==
Koristi idelano objedinjavanje za spajanje stubova kreiranih u fazi I. Idelno objedinjavanje je algoritam koji se pokayuje kao najbolji za objedinjavanje uređenih redova.
Линија 34 ⟶ 33:
Algoritam idealnog objedinjavanja
# Uredi glave ulaznih redova u niz ili povezanu listu.
# Sortiraj listu ulaznih redova u odnosu na relativnu vrednost elementnata sa vrha svakog reda(kako je lista redova tipično mala skoro svaki sort se može upotrebiti za ovo).
# Ispiši element sa vrha prvog reda.
# Ako je prvi red prazan onda ga odbaci. Ako nema više redova izađi, u suprotnom drugi red sada postaje prvi predji na, korak 3, u suprotnom pređi na korak 5.
# Ako je prvi red jedini preostao, pređi na korak 3.
# Uporedi novi vrh prvog reda sa novim vrhom drugog reda. Ako je manji pređi na korak 3.
# Binarnom pretragom pronađi drugi, pronađi gde ternutni vrh provg reda pripad u listi redova I ubaci prvi red na tom mestu u listi. Drugi red je sada prvi, pređi na korak 3.
== Optimizacije ==
=== Optimizacija Faze I ===
Prati da li je poslednji element postavljen na početku ili na kraju nekog stuba i počni poređenje za sledeći element na istoj strani (na primer ukoliko je poslednji element postavljen na kraju stuba počni
poređenje sa poslednjim elementom iz poslednjeg stuba a ne sa početnim i pređi na poređenje sa počenim ukoliko je element veći od poslednjeg u poslednjem stubu). U opštem slučaju i za jako uređene podatke ovo je jedina optimizacija osnpvnog algoritma, u porseku, N/2 poređenja I najviše N-1
poređenja za obrnuto uređene ulaze.
=== Optimizacija Faze II ===
Opšti algoritam Idealnog Objedinjavanja može se ponoljšati boljim upozanvanjem Faze Podele:
Линија 55 ⟶ 54:
S obzirom da porolaz kroz elemnte može biti pripremljen za svaki stub pre nego što je bilo koji drugi stub pripremljen ili pridodat je prednost za poređenje sledećeg elmenta iz prvog stuba sa početnim iz drugog stuba, nakon ispisivanja početnog elementa iz stuba, da bi se odredilo da li je poterbno preuređeivanje pretrage, a ako nije onda elment može odmah da se ispiše i postupak se ponavlja.
=== Optimeizacija za specijalne ulaze ===
Nizovi mogu biti tretirani i kao „tok“ i podvrgnuti iterativnom sortiranju, a ne kreiranju povezane liste
od niza. Zbog poziva funkcije u najboljem slučaju prednost ovoga može biti marginalna, ali korišćenje ne-iterativne vrezije koja niz tretira kao tok može biti i bolja.
Линија 63 ⟶ 62:
Eliminacija dupliranog zapis se može izvesti i tokom Faze I i tokom Faze II ili odložiti do Faze II.
== Literatura ==
{{refbegin}}
* [http://www.nist.gov/dads/HTML/unshufflsort.html -{UnShuffle Sort on nist.gov}-]
* -{''UnShuffle.
{{refend}}
| |||