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

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

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

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

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

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

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

Рассмотрим код работы алгоритма. Сортируемыми объектами будем рассматривать строки. Длина каждой строки равна p . <wikitex>

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

</wikitex> Base - основание системы счисления в случаи со строками 256. [[Файл:Цифровая_сортировка.png|thumb|right|450px|