Segmentno sortiranje

Elementi su podeljeni između kanti

Onda, elementi su sortirani u okviru svake kante

Segmentno sortiranje (engl. Bucket sort - kofa sortiranje, kanta sortiranje) je algoritam za soritranje koji funkcioniše tako što deli niz u određeni broj kofa (kanti). Svaka kofa se onda sortira pojedinačno, koristeći neki drugi algoritam za sortiranje, ili rekurzivnom primenom kofa sortiranja. To je distributivno sortiranje, i rođak je radiks sortiranja u izboru cifre od najveće do najmanje težine. Kofa sortiranje je generalizaciija pretinac sortiranja.Pošto kofa sortiranje nije sortiranje poređenjem, donja granica Ω(n log n) je neprimenljiva.Procena složenosti izračunavanja uključuje broj kofa.

Kofa sortiranje radi na sledeći način:

1. Definisati niz inicijalno praznih “ Kofa (Segmenata,Kanti)”
2. Rasturanje: Pretražiti prvobitni niz, stavljajući svaki element u odgovarajuću kofu.
3. Sortirati svaku kofu koja nije prazna.
4. Skupljanje: Posetiti svaku od kofa u odgovarajućem redosledu I smestiti sve elemente u prvobitni niz.

Pseudokod

function bucketSort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ...., buckets[n-1]

Promenljiva array je niz koji treba da se sortira ,a promenljiva n je broj kofa koje se koriste.Funkcija msbits(x,k) vraća k najznačajnijih bitova od x (floor(x/2^(size(x)-k))); različite funkcije mogu biti korišćene za prevođenje opsega elemenata niza u n kofa, kao što je prevođenje slova (A-Z) u brojeve (0-25) ili vraćanje prvog karaktera(0-255),prilikom sortiranja stringova.Funkcija nextSort služi za soritranje; koristeći kofa sortiranje ona proizvodi rođaka radiks sortiranja; posebno kada imamo slučaj da je n = 2 koji odgovara brzom sortiranju,iako sa potencijalno loše izabranim pivotom.

Optimizacija

Zajednička optimizacija je da stavi nesortirane elemente kofa u prvobitni niz, pa onda da sortira celi niz koristeći sortiranje umetanjem, jer vreme izvršavanja sortiranja umetanjem zavisi od toga koliko je daleko svaki element od svoje završne pozicije.Broj poređenje ostaje relativno mali I hijerarhija memorije je bolje iskorišćena za čuvanje listi koje su razdvojene u memoriji.

Varijante

Generičko kofa sortiranje

Najčešća varijanta kofa sortiranja radi na listi od n numeričkih ulaza između nule I neke maksimalne vrednosti M I deli opseg u n kofa, gde je svaka veličine M/n.Ako je svaka kofa sortirana koristeći sortiranje umetanjem, onda se može pokazati da se izvršava u očekivanom linearnom vremenu(gde se uzima prosek u odnosu na sve moguće ulaze). Međutim , preformanse ovog soritiranja opada sa grupisanjem; ako se mnogo vrednosti javlja zajedno, onda će one da sve upadnu u jednu kofu i sortiranje će biti sporo.

Proksmap sortiranje

Slično kao i generičko kofa sortiranje,opisano iznad,Proksmap soritranje radi tako što deli niz članova u podnizove koristeći funkciju za mapiranje koja čuva delimično uređenje članova; kako se svaki član dodaje u podniz, sortiranje umetanjem se koristi da se taj podniz sortira, čineći tako da se ceo niz sortira u odgovarajućem redosledu kada se Proksmap soritranje završi.Proksmap sortiranje se razlikuje od kofa soritranja u korišćenju članova za postavljanje podataka otprilike na ona mesta gde pripadaju u sortiranom redosledu, proizvodeći “proksmap” – blizina mapiranja – od članova.

Histogram sortiranje

Još jedna varijanta kofa sortiranja je histogram sortiranje ili sortiranje računanjem, koje dodaje početni prolaz, koji broji broj elemenata koji će doći u svaku kofu koristeći niz brojanja.Koristeći ovu informaciju, vrednosti niza mogu biti raspoređene u niz kofa od strane niza razmene, ne ostavljajući prostor ispred za smeštanje kofa.

Poštarevo sortiranje

Poštarevo soritranje je varijanta kofa soritranja koje uzima prednost hijerarhijske strukture elemenata, obično opisanih skupom atributa.Ovo je algoritam koji se koristi od strane mašina koje soritraju pisma u poštama; pošta se prvo sortira između domaće i internacionalne; onda po državi, proviniciji ili teritoriji;onda po poštanskoj stanici kojoj treba da se dostavi; onda po rutama,itd.Pošto se članovi ne porede jedan u odnosu na drugi, vreme soritranja je O(cn), gde c zavisi od veličine člana I broja kofa.Ovo je slično kao I radiks soritranje, koje radi “odozgo-nadole” ili “najznačajnije cifre prvo”.

Sortiranje mešanjem

Soritranje mešanjem je varijanta kofa sortiranja koje počinje soritranje tako što uklanja 1/8 n elemenata koje treba sortirati, sortira ih rekurzivno, i stavlja ih u niz. Ovo kreira n/8 “kofa” u koje se preostalih 7/8 elemenata smešta.Svaka “kofa” je onda sortirana, I “kofe” spojene u sortirani niz.Soritranje mešanjem se koristi kao prvi korak u J sortiranju.

Poređenje sa drugim algoritmima za sortiranje

Kofa sortiranje može se posmatrati kao generalizacija sortiranja računanjem; zapravo, ako je svaka kofa veličine 1 onda se kofa sortiranje ponaša kao sortiranje računanjem.Promenljiva veličina kofe u kofa sortiranju dozvoljava da se koristi O(n) memorije umesto O(M) memorije, gde je M broj različitih vrednosti;u zamenu, odustaje se od najgoreg slučaja O(n + M) sortiranja računanjem.

Kofa sortiranje sa dve kofe je efektivna verzija brzog sortiranja, gde je vrednost pivota uvek izabrana da bude srednja vrednost opsega vrednosti.Dok je izbor efektivan za ravnomerno raspodeljene ulaze, drugi načini izbora pivota u brzom sortiranju,kao što su slučajno izabrani pivoti, čine je otpornijom prilikom grupisanja u ulaznoj raspodeli.

Algoritam koji sortira spajanjem počinje tako što deli listu u n podlisti i sortira svaku;međutim, podliste kreirane od strane algoritma koji sortira spajanjem imaju vrednosti koje se preklapaju i zbog toga ne mogu biti spojene konkatenacijom kao u kofa sortiranju.Umesto toga, moraju biti ispreplitane od strane algoritma spajanja.Međutim , ovaj rashod je izbalansiran jednostavnom fazom rasturanja i sposobnošću da se osigura da su sve podliste jednake veličine dajući dobro vremensko ograničenje najgoreg slučaja.

Odozgo-nadole radiks soritranje moze da se posmatra kao specijalni slučaj kofa sortiranja gde su i opseg vrednosti i broj kofa ograničeni na vrednost 2.Stoga, svaka veličina kofe je takodje 2, i procedura moze da se primeni rekurzivno. Ovaj pristup može da ubrza fazu rasturanja, pošto moramo jedino da ispitamo prefiks bitovske reprezentacije svakog elementa da bi smo odredili njegovu kofu.

Literatura

• Paul E. Black "Postman's Sort" from Dictionary of Algorithms and Data Structures at National Institute of Standards and Technology.
• Robert Ramey '"The Postman's Sort" C Users Journal Aug. 1992
• NIST's Dictionary of Algorithms and Data Structures: bucket sort

Spoljašnje veze

• Bucket Sort Code for Ansi C
• Variant of Bucket Sort with Demo