Sortiranje podelom

Из Википедије, слободне енциклопедије

Sortiranje (razvrstavanje) podelom (engl. 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' (engl. 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).

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[уреди]

  1. Uzmi prvi element i kreiraj stub #1 sa elementom#1 kao glavu i rep.
  2. Ako nema više elementa pređi na fazu II.
  3. Uzmi sledeći element.
  4. Odaberite posljednji stub za poređenje.
  5. Uporedi sa vrhom stuba.
  6. Ako jednak stvi na vrh stuba, pređi na korak 2.
  7. Ako je manji, a to nije prvi stub označi prethodni stub i pređi na korak 5.
  8. Ako je manje i to jeste prvi stub, stavi element na vrh stuba i pređi na korak 2.
  9. 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.
  10. Uporedi sa krajem trenutnog stuba.
  11. Ako jednak stavi na kraj stuba, pređi na korak 2.
  12. Ako je veći, a to nije prvi stub oynači prethodni stub, pređi na korak 10.
  13. Ako je manji i to je posljednji stub kreiraj novi stub od elementa i dodati u listu stubova, pređi na korak 2.
  14. 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.

Algoritam idealnog objedinjavanja

  1. Uredi glave ulaznih redova u niz ili povezanu listu.
  2. 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).
  3. Ispiši element sa vrha prvog reda.
  4. 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.
  5. Ako je prvi red jedini preostao, pređi na korak 3.
  6. Uporedi novi vrh prvog reda sa novim vrhom drugog reda. Ako je manji pređi na korak 3.
  7. 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:

Kada se koristi za obejdinjavanje Unshuffle sorta, kreiranje liste redova i početno sortiranje stubova nije potrebno s obzirom da podela kreira stubove uređene po njihovim početnim elemnetima. U ovom slučaju objedinjavanje počinje u koraku #3.

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.

Unshuffle nije stabilan algoritam sortiranja ali stabilnost se može postići ubacivanjem ulaznog zapisa na kraj ključa sortiranja.

Eliminacija dupliranog zapis se može izvesti i tokom Faze I i tokom Faze II ili odložiti do Faze II.

Literatura[уреди]