Карманная сортировка

Карманная сортировка(Bucket sort) — алгоритм сортировки , основанный на предположении о равномерном распределении входных данных.

Алгоритм сортировки

Принцип работы

Пример работы рекурсивного Bucketsort.

• элементы массива входных данных разбиваются на [math]k[/math] блоков ("карманов","корзин").
• каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
• из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.

Важно отметить ,что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.

Реализация

Рассмотрим код работы алгоритма, где [math] p [/math] — длина каждой строки. <wikitex>

Bucketsort(A, j){ // A - массив данных, j - текущий разряд
    if (A.length() < 2 || j == p + 1)
        return A;
    buckets <- инициализируем массив длины Base, где каждая ячейка — список входных объектов (в нашем случае    
    строк).
    for i = 0  to A.length() - 1  
      добавляем A[i] в конец массива buckets[partition(A[i],j)] 
    // partition — функция которая по данному объекту и индексу возвращает число от 0 до Base - 1
    // в случае со строками функция partition возвращает код j-ого символа строки A[i].  
    for i = 0 to Base - 1
       buckets[i] = Bucketsort(buckets[i],j+1)
    answer <- инициализируем пустой массив (в который записывается отсортированный набор данных)
    for i = 0 to Base - 1
       for k = 0 to buckets[i].length() - 1
          добавляем  buckets[i][k] в конец массива answer
    return answer
}

</wikitex> Base - основание системы счисления в случае со строками Base = 256.

Приведенный код, работает не только для строк , а в принципе для любых объектов для которых можно определить порядок, систему счисления и функцию partition.

Асимптотика

Пусть [math]n[/math] количество элементов в массиве, [math]k[/math] основание системы исчисления и [math]p[/math] количество разрядов в объекте. Тогда алгоритм "Bucket sort" в процессе работы, сделает не более чем [math]O(p * (n + k))[/math] итераций. Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке [math] n/k[/math]. Следовательно в средним алгоритм "карманной сортировки" совершает [math]O(n * log_k n)[/math] действий.При этом на некотором множестве наборов, где [math] k = O(n)[/math] , алгоритм отработает за линейное время. В худшем случаи , сортировка работает за [math]O(n^2)[/math].

Примечания

Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системы счисления. быстрая сортировка является частным случаем "карманной" сортировкой, в случаи разбиения всех элементов на [math]2 [/math] "кармана".Также стоит отметить, что по принципу своей работы Bucket sort схожа с Цифровой сортировкой.

Ссылки

• http://en.wikipedia.org/wiki/Bucket_sort

• Презентация о линейных сортировках.