Файл: Алгоритмы сортировки данных, блочная сортировка.pdf

For i = 0 To <количество значений> - 1

// Прибавляем 1 к счетчику данного значения.

counts[values[i]] = counts[values[i]] + 1

Next i

// Копируем значения в исходный массив.

Integer: index = 0

For i = 0 To max_value

// Копируем значение i в массив counts[i] раз.

For j = 1 To counts[i]

values[index] = i

index = index + 1

Next j

Next i

End Countingsort

Параметр max_value содержит наибольшее значение из массива (если оно не задано, алгоритм определит его, просмотрев массив); M — общее количество элементов в массиве counts (M = max_value + 1), а N — в массиве values. Если используемый вами язык программирования не инициализирует массив counts так, чтобы он содержал нули, алгоритм затратит на это М шагов, после чего выполнит еще N шагов, чтобы посчитать значения

В завершение работы алгоритм копирует значения обратно в исходный массив (каждое один раз), поэтому данная часть процесса займет N шагов. Если какая-либо из записей в массиве counts все еще равна 0, программа потратит определенное время на перепрыгивание через нее. В худшем случае, когда все значения одинаковы, а массив counts содержит в основном нули, для аналогичного действия понадобится M шагов. Отсюда общее время работы алгоритма: O(2N + M) = O(N + M).

Если M относительно мало по сравнению с N, полученная производительность окажется лучше O(N _ log N), которую демонстрирует пирамидальная сортировка и другие описанные выше алгоритмы.

На практике для тестового массива с 1 млн элементов и диапазоном значений от 0 до 1000, быстрая сортировка заняла в несколько сот раз больше времени, чем сортировка подсчетом.

Следует отметить, что для быстрой сортировки выбранный пример оказался не самым лучшим, поскольку среди значений было множество дубликатов (приблизительно 1000), а данный алгоритм справляется с ними плохо. Пирамидальная сортировка аналогичного массива показала себя эффективнее быстрой сортировки, но все равно значительно уступила сортировке подсчетом.

4.2 Блочная сортировка

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

Листинг 10 – Псевдокод блочной сортировки

Bucketsort(Data: values[])

<Создаем блоки.>

<Распределяем элементы по блокам.>

<Сортируем блоки.>

<Собираем элементы блоков в исходный массив.>

End Bucketsort

Если при использовании M блоков значения в массиве из N элементов распределены относительно равномерно и их диапазон делится поровну, можно ожидать, что в каждый блок попадет N/M элементов.

В качестве примера возьмем массив, изображенный вверху на рисунке 12. Он содержит 10 элементов со значениями от 0 до 99. На первом этапе алгоритм делит элементы на блоки, которые в нашем случае состоят из 20 значений: от 0 до 19, от 20 до 39 и т. д. На втором этапе алгоритм сортирует каждый блок, а на третьем объединяет их значения для построения результата сортировки.

Блоками могут выступать стеки, связные списки, очереди, массивы или любые другие структуры данных.

Рисунок 12 – Блочная сортировка

Чтобы разбить N равномерно распределенных элементов по блокам, алгоритму понадобится N шагов, если не учитывать перенос элемента в блок. Обычно такое преобразование занимает фиксированный отрезок времени. Предположим, в массиве находятся целые числа от 0 до 99, как в примере на рисунке 12. Вам надо перенести элемент со значением v в блок номер |v/20|. Этот номер можно рассчитать за определенное время, таким образом, для распределения элементов потребуется O(N) шагов.

Если таких блоков M, для сортировки каждого из них понадобится F(N/M) шагов, где F — функция времени работы алгоритма, который вы используете при сортировке блоков. Получается, что общее время сортировки всех блоков составит O(M x F(N/M)).

Чтобы собрать все отсортированные значения назад в массив, надо выполнить N основных шагов и, возможно, O(M) дополнительных, чтобы пропустить пустые блоки. Но если M < N, для всей операции потребуется O(N) шагов.

При суммировании всех этапов получим следующее: O(N) + O(M _ F(N/M)) + + O(N) = O(N + M _ F(N/M)). Если M является фиксированной долей N, то N/M, а следовательно, и F(N/M) — константы. Тогда формула упрощается до O(N + M).

На практике число M должно составлять относительно большую долю N, чтобы алгоритм мог хорошо работать. Если у вас 10 млн записей и 10 блоков, то в каждом из них будет в среднем по 1 млн записей. В отличие от сортировки подсчетом, производительность блочной сортировки не зависит от количества используемых блоков.

Заключение

Алгоритмы сортировки, описанные в работе, используют разные методы и обладают различными характеристиками. Все они сведены в таблицу 1.