Back

ⓘ Segmentno sortiranje




Segmentno sortiranje
                                     

ⓘ Segmentno sortiranje

Segmentno sortiranje je algoritam za soritranje koji funkcioniše tako što deli niz u odredeni broj kofa. Svaka kofa se onda sortira pojedinačno, koristeći neki drugi algoritam za sortiranje, ili rekurzivnom primenom kofa sortiranja. To je distributivno sortiranje, i rodak 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 poredenjem, donja granica Ω je neprimenljiva.Procena složenosti izračunavanja uključuje broj kofa.

Kofa sortiranje radi na sledeći način:

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

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 On memorije umesto OM memorije, gde je M broj različitih vrednosti;u zamenu, odustaje se od najgoreg slučaja On + 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;medutim, 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.Medutim, 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.

                                     

1. Literatura

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