Сегментно сортирање

Елементи су подељени између канти

Онда, елементи су сортирани у оквиру сваке канте

Сегментно сортирање (енгл. Bucket sort - кофа сортирање, канта сортирање) је алгоритам за соритрање који функционише тако што дели низ у одређени број кофа (канти). Свака кофа се онда сортира појединачно, користећи неки други алгоритам за сортирање, или рекурзивном применом кофа сортирања. То је дистрибутивно сортирање, и рођак је радикс сортирања у избору цифре од највеће до најмање тежине. Кофа сортирање је генерализациија претинац сортирања.Пошто кофа сортирање није сортирање поређењем, доња граница Ω(н лог н) је неприменљива.Процена сложености израчунавања укључује број кофа.

Кофа сортирање ради на следећи начин:

1. Дефинисати низ иницијално празних “ Кофа (Сегмената,Канти)”
2. Растурање: Претражити првобитни низ, стављајући сваки елемент у одговарајућу кофу.
3. Сортирати сваку кофу која није празна.
4. Скупљање: Посетити сваку од кофа у одговарајућем редоследу I сместити све елементе у првобитни низ.

Псеудокод

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]

Променљива арраy је низ који треба да се сортира ,а променљива н је број кофа које се користе.Функција мсбитс(x,к) враћа к најзначајнијих битова од x (флоор(x/2^(сизе(x)-к))); различите функције могу бити коришћене за превођење опсега елемената низа у н кофа, као што је превођење слова (А-З) у бројеве (0-25) или враћање првог карактера(0-255),приликом сортирања стрингова.Функција неxтСорт служи за соритрање; користећи кофа сортирање она производи рођака радикс сортирања; посебно када имамо случај да је н = 2 који одговара брзом сортирању,иако са потенцијално лоше изабраним пивотом.

Оптимизација

Заједничка оптимизација је да стави несортиране елементе кофа у првобитни низ, па онда да сортира цели низ користећи сортирање уметањем, јер време извршавања сортирања уметањем зависи од тога колико је далеко сваки елемент од своје завршне позиције.Број поређење остаје релативно мали I хијерархија меморије је боље искоришћена за чување листи које су раздвојене у меморији.

Варијанте

Генеричко кофа сортирање

Најчешћа варијанта кофа сортирања ради на листи од н нумеричких улаза између нуле I неке максималне вредности M I дели опсег у н кофа, где је свака величине M/н.Ако је свака кофа сортирана користећи сортирање уметањем, онда се може показати да се извршава у очекиваном линеарном времену(где се узима просек у односу на све могуће улазе). Међутим , преформансе овог соритирања опада са груписањем; ако се много вредности јавља заједно, онда ће оне да све упадну у једну кофу и сортирање ће бити споро.

Проксмап сортирање

Слично као и генеричко кофа сортирање,описано изнад,Проксмап соритрање ради тако што дели низ чланова у поднизове користећи функцију за мапирање која чува делимично уређење чланова; како се сваки члан додаје у подниз, сортирање уметањем се користи да се тај подниз сортира, чинећи тако да се цео низ сортира у одговарајућем редоследу када се Проксмап соритрање заврши.Проксмап сортирање се разликује од кофа соритрања у коришћењу чланова за постављање података отприлике на она места где припадају у сортираном редоследу, производећи “проксмап” – близина мапирања – од чланова.

Хистограм сортирање

Још једна варијанта кофа сортирања је хистограм сортирање или сортирање рачунањем, које додаје почетни пролаз, који броји број елемената који ће доћи у сваку кофу користећи низ бројања.Користећи ову информацију, вредности низа могу бити распоређене у низ кофа од стране низа размене, не остављајући простор испред за смештање кофа.

Поштарево сортирање

Поштарево соритрање је варијанта кофа соритрања које узима предност хијерархијске структуре елемената, обично описаних скупом атрибута.Ово је алгоритам који се користи од стране машина које соритрају писма у поштама; пошта се прво сортира између домаће и интернационалне; онда по држави, провиницији или територији;онда по поштанској станици којој треба да се достави; онда по рутама,итд.Пошто се чланови не пореде један у односу на други, време соритрања је О(цн), где ц зависи од величине члана I броја кофа.Ово је слично као I радикс соритрање, које ради “одозго-надоле” или “најзначајније цифре прво”.

Сортирање мешањем

Соритрање мешањем је варијанта кофа сортирања које почиње соритрање тако што уклања 1/8 н елемената које треба сортирати, сортира их рекурзивно, и ставља их у низ. Ово креира н/8 “кофа” у које се преосталих 7/8 елемената смешта.Свака “кофа” је онда сортирана, I “кофе” спојене у сортирани низ.Соритрање мешањем се користи као први корак у Ј сортирању.

Поређење са другим алгоритмима за сортирање

Кофа сортирање може се посматрати као генерализација сортирања рачунањем; заправо, ако је свака кофа величине 1 онда се кофа сортирање понаша као сортирање рачунањем.Променљива величина кофе у кофа сортирању дозвољава да се користи О(н) меморије уместо О(M) меморије, где је M број различитих вредности;у замену, одустаје се од најгорег случаја О(н + M) сортирања рачунањем.

Кофа сортирање са две кофе је ефективна верзија брзог сортирања, где је вредност пивота увек изабрана да буде средња вредност опсега вредности.Док је избор ефективан за равномерно расподељене улазе, други начини избора пивота у брзом сортирању,као што су случајно изабрани пивоти, чине је отпорнијом приликом груписања у улазној расподели.

Алгоритам који сортира спајањем почиње тако што дели листу у н подлисти и сортира сваку;међутим, подлисте креиране од стране алгоритма који сортира спајањем имају вредности које се преклапају и због тога не могу бити спојене конкатенацијом као у кофа сортирању.Уместо тога, морају бити испреплитане од стране алгоритма спајања.Међутим , овај расход је избалансиран једноставном фазом растурања и способношћу да се осигура да су све подлисте једнаке величине дајући добро временско ограничење најгорег случаја.

Одозго-надоле радикс соритрање мозе да се посматра као специјални случај кофа сортирања где су и опсег вредности и број кофа ограничени на вредност 2.Стога, свака величина кофе је такодје 2, и процедура мозе да се примени рекурзивно. Овај приступ може да убрза фазу растурања, пошто морамо једино да испитамо префикс битовске репрезентације сваког елемента да би смо одредили његову кофу.

Литература

• 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

Спољашње везе

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