Sortiranje podelom — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
|||
Ред 1:
{{МАТФ052013}}
'''Sortiranje 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
▲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'(eng. 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 listi sa pokayivačima na početak i kraj dvostruko povezane liste sadrži elemente stuba kao i sledeći i prethodni stub. Detalji uklanjanja elemnata iz ulazne liste i dodavanjem elemenata u izlaznu listu su izostavljeni kao posebne implementacije.
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).
Ред 13:
==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.
| |||