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

Карманная сортировка (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 \cdot (n + k))[/math] итераций. Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке [math] n/k[/math]. Следовательно, в средним алгоритм "карманной сортировки" совершает [math]O (n \cdot \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

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