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.

Оптимизации[редактиране | редактиране на кода]

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

Варианти[редактиране | редактиране на кода]

Общ bucket sort[редактиране | редактиране на кода]

Най-разпространеният вариант на bucket sort, който оперира с лист от n числа между 0 и максимално число M, разделяйки стойностите в интервали – n „контейнера“, всеки един с размер от M/n. Ако всеки масив е сортиран чрез сортиране чрез вмъкване, bucket sort ще работи в линейно време.[2] Производителността на този вид сортиране ще намалее значително, ако много групи стойности са прекалено близо една до друга, всички ще попаднат в един „контейнер“ и сортирането им ще се забави.

ProxmapSort[редактиране | редактиране на кода]

 Основна статия: Proxmap sort

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

Histogram сортиране[редактиране | редактиране на кода]

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

Postman's сортиране[редактиране | редактиране на кода]

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

Shuffle сортиране[редактиране | редактиране на кода]

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

Сравнение с други сортиращи алгоритми[редактиране | редактиране на кода]

Bucket sort може да се разглежда като валиден за общи случаи, модел на counting sort.

Bucket sort с два „контейнера“ е модел на quicksort, където разделящата ги стойност е винаги медианата в интервала от стойности. Изборът на този алгоритъм е подходящ, ако стойностите са разпределени равномерно, в противен случай този избор на разделящата стойност може да доведе до неравномерно разпределение в двата „контейнера“.

Друг подобен алгоритъм е сортиране чрез сливане, който разпределя листа в n суб-листа и сортира всеки един от тях. Въпреки това, алгоритмите чрез сливане имат застъпващи се интервали на стойностите и не могат да бъдат обединени чрез конкатенация. Въпреки това, по-лесната фаза на разделяне на елементите и осигурявайки една и съща големина на листовете, компенсира допълнителното изчислително време.

Radix sort може да бъде разглеждан като частен случай на bucket sort, където интервала на стойностите и броя на „контейнери“ трябва да бъде степен на 2. Като следствие големината на „контейнерите“ също е степен на 2 и може да се приложи рекурсия. Този подход може да ускори стъпката на разделяне на елементите, защото е необходима само проверка на началото на битовото представяне на всеки от елементите.

Източници[редактиране | редактиране на кода]

  1. ↑ Corwin, E. and Logar, A. „Sorting in linear time – variations on the bucket sort“. Journal of Computing Sciences in Colleges, 20, 1, pp.197 – 202. October 2004.
  2. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174 – 177.
  3. ↑ Robert Ramey Software Development // rrsd.com. Посетен на 25 януари 2022.

Външни препратки[редактиране | редактиране на кода]

  Тази страница частично или изцяло представлява превод на страницата Bucket sort в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​

Взето от „https://bg.wikipedia.org/w/index.php?title=Bucket_сортиране&oldid=11280626“.