Эффективность поразрядной сортировки

Поразрядная сортировка для массивов

Одним из известных алгоритмов является метод, называемый «сортировкой подсчетом».

Пусть у нас есть массив source из n десятичных цифр (m = 10).
Например, source[7] = {7, 9, 8, 5, 4, 7, 7}, n=7. Здесь положим const k=1.

1. Создать массив count из m элементов (счетчиков).

2. Присвоить count[i] количество элементов source, равных i. Для этого:

· проинициализовать count[] нулями;

· пройти по source от начала до конца, для каждого числа увеличивая элемент count с соответствующим номером;

· for(i=0; i<n; i++) count [ source[i] ]++;

В нашем примере count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }.

3. Присвоить count[i] значение, равное сумме всех элементов до данного: count[i] = count[0]+count[1]+...count[i-1]. В нашем примере count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }. Эта сумма является количеством чисел исходного массива, меньших i.

4. Произвести окончательную расстановку.

Для каждого числа source[i] мы знаем, сколько определено чисел меньше него - это значение хранится в count[ source[i] ]. Таким образом, нам известно окончательное место числа в упорядоченном массиве: если есть K чисел меньше данного, то оно должно стоять на позиции K+1.
Осуществляем проход по массиву source слева направо, одновременно заполняя выходной массив dest:

for (i=0; i<n; i++) { c = source[i]; dest[ count[c] ] = c; count[c]++; // для повторяющихся чисел }

Таким образом, число c=source[i] ставится на место count[c]. На этот случай, если числа повторяются в массиве, предусмотрен оператор count[c]++, который увеличивает значение позиции для следующего числа c, если таковое будет.

Циклы занимают (n + m) времени. Столько же требуется памяти.

Итак, мы научились за (n + m) сортировать цифры. А от цифр до строк и чисел - 1 шаг. Пусть у нас в каждом ключе k цифр (m = 10). Аналогично случаю со списками отсортируем их в несколько проходов от младшего разряда к старшему (рис. 23).

Исходная k =3 последовательность	Первый проход по 3-му разряду	Второй проход по 2-му разряду	третий проход по 1-му разряду
	↑	↑	↑
Offset (номер позиции)

Рис. 23

Общее количество операций составляет k(n+m), при используемой дополнительно памяти (n+m). Эта схема допускает небольшую оптимизацию. Заметим, что сортировка по каждому байту состоит из 2 проходов по всему массиву: на первом шаге и на четвертом. Однако можно создать сразу все массивы count[] (по одному на каждую позицию) за один проход. Неважно, как расположены числа - счетчики не меняются, поэтому это изменение корректно. Таким образом, первый шаг будет выполняться один раз за всю сортировку, а значит, общее количество проходов изменится с 2k на k+1.

Рост быстрой сортировки мы уже знаем: O(nlogn). Судя по оценке, поразрядная сортировка растет линейным образом по n, так как k, m - константы.

Также она растет линейным образом по k - при увеличении длины типа (количества разрядов) соответственно возрастает число проходов. Однако в последний пункт реальные условия вносят свои коррективы.

Дело в том, что основной цикл сортировки по i -му байту состоит в движении указателя uchar* bp шагами sizeof(T) по массиву для получения очередного разряда. Когда T=char, шаг равен 1, T=short - шаг равен 2, T=long - шаг равен 4. Чем больше размер типа, тем менее последовательный доступ к памяти осуществляется, а это весьма существенно сказывается на скорости работы. Поэтому реальное время возрастает чуть быстрее, нежели теоретическое.

Кроме того, поразрядная сортировка уже по своей сути неинтересна для малых массивов. Каждый проход содержит минимум 256 итераций, поэтому при небольших n общее время выполнения (n+m) определяется константой m=256.

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

Дата добавления: 2014-12-27