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

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

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

Принцип работы алгоритма вообщем

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

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

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

Реализация Алгоритма

Рассмотрим код работы алгоритма.

<wikitex>

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