Bucket сортиране

Bucket sort, или bin sort, е сортиращ алгоритъм, който работи чрез разделяне на един масив в определен брой контейнери. След това всеки „контейнер“ се сортира индивидуално, или чрез използване на различни сортиращи алгоритми, или чрез рекурсивно прилагане на bucket сортиране. Bucket сортиране е обобщаващ на pigeonhole sort, алгоритъм. Пресмятането на изчислителната сложност включва броя на използваните „контейнери“. Bucket sort може да се изпълнява с линейно време – (Θ(n)). Всяка кофа трябва да съдържа или един елемент, или да се сортира.

Елементите се групират в „контейнери“

Елементите във всеки един „контейнер“ се сортират

Bucket sort работи по следния начин:

1. Създава масив от празни „контейнери“.
2. Разделя: Минава през елементите на оригиналния масив, слагайки всеки елемент в „контейнер“.
3. Сортира „контейнер“, който не е празен.
4. Събира: Минава през всеки един от „контейнерите“ и връща елементите в оригиналния масив.

function bucketSort(array, n) is
  контейнери ← нов масив от n празни списъка
  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 конкатенация на контейнерите: buckets[0], ...., buckets[n-1]

Тук array е масивът, който ще бъде сортиран и n е броят на „контейнерите“, които ще бъдат използвани. Функцията msbits(x,k) връща k, което е позицията на бита с най-голяма стойност, в x (floor(x/2^(size(x)-k))); различни функции могат да бъдат използвани за превеждането на интервала на елементите на масива в n „контейнера“, като напр. превеждането на буквите A–Z в 0 – 25 или връщането на първата буква (0 – 255) за сортиране на стрингови променливи. Функцията nextSort е сортираща функция; използването на самия bucketSort като nextSort създава подобен на алгоритъма radix sort; в частност случаят, при който n = 2 е аналогичен на quicksort

Оптимизации
Честа оптимизация е да се сложат несортираните елементи от „контейнерите“ първо в оригиналния масив, след което да се изпълни сортиране чрез вмъкване върху целия масив. Времето за компилиране на сортиране чрез вмъкване е основано на какво разстояние се намира всеки един от елементите спрямо финалната си позиция. Броят на извършените сравнения остава сравнително малък, а йерархията на паметта е използвана по-добре, заради запазване на листа последователно в паметта.

Варианти

Общ bucket sort
Най-разпространеният вариант на bucket sort, който оперира с лист от n числа между 0 и максимално число M, разделяйки стойностите в интервали – n „контейнера“, всеки един с размер от M/n

ProxmapSort
Подобен на общия bucket sort, ProxmapSort работи чрез разделяне на масив от ключове в суб-масиви, използвайки функцията „map key“. „Map key“ запазва частичния ред на ключовете, където всеки ключ е добавен към неговия суб-масив, сортиране чрез вмъкване се използва, за се пазят суб-масивите сортирани постоянно. В

Histogram сортиране
Друг вариант на bucket sort е histogram sort, който в три стъпки сортира множеството от елементи. В първата стъпка, пази броя на елементите, които щя влязат в даден „контейнер“, в отделен спомагателен масив. След това използва тези броячи, за да определи точната големина на всеки един от „контейнерите“. Последната стъпка сортира всеки отделен „контейнер“.

Postman’s сортиране
Postman сортиране е вариант на bucket sort, който използва йерархичната структура на елементите. Това е алгоритъм, който се използва при машините сортиращи писма – първо се делят на национална и международна поща; след това на община, град, квартал и т.н.

Shuffle сортиране
Shuffle сортиране започва с отделянето на 1/8 от всички елементи и на база средното отношение на елементите към медианата се определят n/8 „контейнери“, които да съхранят всички останали елементи. „Контейнерите“ се сортират и конкатенират в сортиран масив.