Новые сообщения · Правила  
Страница 1 из 11
Форум ПРОГРАММИСТОВ » ПРОГРАММИРОВАНИЕ » Алгоритмы » Алгоритмы сортировок (Корневая сортировка)
Алгоритмы сортировок
Корневая сортировка

При корневой сортировке упорядочивание списка происходит без непосредственного сравнения ключевых значений между собой. При этом создается набор «стопок», а элементы распределяются по стопкам в зависимости от значений ключей. Собрав значения обратно и повторив всю процедуру для последовательных частей ключа, мы получаем отсортированный список. Чтобы такая процедура работала, распределение по стопкам и последующую сборку следует выполнять очень аккуратно.

Подобная процедура используется при ручной сортировке карт. В некоторых библиотеках в докомпьютерные времена при выдаче книги заполнялась карта выдачи. Карты выдачи были занумерованы, а сбоку на них проделывался ряд выемок – в зависимости от номера карты. При возвращении книги карта выдачи удалялась, и ее клали в стопку. Затем вся стопка прокалывалась длинной иглой на месте первой выемки, и иглу поднимали. Карты с удаленной выемкой оставались на столе, а остальные были наколоты на иглу. Затем две получившиеся стопки переставлялись так, что карточки на игле шли за карточками с отверстиями. Затем игла втыкалась в месте второй выемки и весь процесс повторялся. После прокалывания по всем позициям карты оказывались в порядке возрастания номеров.

Добавлено (14.03.2008, 23:57)
---------------------------------------------
Эта процедура ручной обработки разделяет карты по значению младшего разряда номера на первом шаге и старшего разряда на последнем. Компьютеризованный вариант этого алгоритма использует 10 стопок:
RadixSortClist,N)
list сортируемый список элементов
N число элементов в списке
shift=l
for loop=l to keySize do
for entry=l to N do
bucketNumber=(list[entry].key/shift) mod 10
Append(bucket[bucketNumber], list[entry])
end for entry
list=CombineBuckets ()
shift=shift*10
end for loop

keySize – самый большой разряд числа;
10 – количество цифр
bucket – стопка.

Добавлено (14.03.2008, 23:58)
---------------------------------------------
Начнем с обсуждения этого алгоритма. При вычислении значения переменной bucketNumber из ключа вытаскивается одна цифра. При делении на shift ключевое значение сдвигается на несколько позиций вправо, а последующее применение операции mod оставляет лишь цифру единиц полученного числа. При первом проходе с величиной сдвига 1 деление не меняет числа, а результатом операции mod служит цифра единиц ключа. При втором проходе значение переменной shift будет уже равно 10, поэтому целочисленное деление и последующее применение операции mod дают цифру десятков. При очередном проходе будет получена следующая цифра числа.

Функция CombineBuckets вновь сводит все стопки от bucket [0] до bucket [9] в один список. Этот переформированный список служит основой для следующего прохода. Поскольку переформирование стопок идет в определенном порядке, а числа добавляются к концу каждой стопки, ключевые значения постепенно оказываются отсортированными.


Думаю, не ошибусь, если промолчу ;)
1 | Автор: Archi | 2008-03-14, 23:58 | Изменено: Archi - Пт, 2008-03-14, 23:56   |  Репутация: [ + 3 ]

Добавлено (15.03.2008, 00:05)
---------------------------------------------
Анализ
Анализ корневой сортировки требует учета дополнительной информации, не только числа операций. Способ реализации алгоритма оказывает существенное влияние на эффективность. Нас будет интересовать эффективность алгоритма как по времени, так и по памяти. Каждый ключ просматривается по одному разу на каждый разряд, присутствующий в самом длинном ключе. Поэтому если в самом длинном ключе М цифр, а число ключей равно N, то сложность корневой сортировки имеет порядок O(MN). Однако длина ключа невелика по сравнению с числом ключей. Например, при ключе из шести цифр число различных записей может быть равно миллиону. Длина ключа не играет роли и алгоритм имеет линейную по длине сложность O(N). Это очень эффективная сортировка, поэтому возникает вопрос, зачем вообще нужны какие-либо другие методы.

Добавлено (15.03.2008, 00:06)
---------------------------------------------
Ключевым препятствием в реализации корневой сортировки служит ее неэффективность по памяти. В предыдущих алгоритмах сортировки дополнительная память нужна была разве что для обмена двух записей, и размер этой памяти равняется длине записи. Теперь же дополнительной памяти нужно гораздо больше. Если стопки реализовывать массивами, то эти массивы должны быть чрезвычайно велики. На самом деле, величина каждого из них должна совпадать с длиной всего списка, поскольку у нас нет оснований полагать, что значения ключей распределены по стопкам равномерно, как на рис. 3.2. Вероятность того, что во всех стопках окажется одинаковое число записей, совпадает с вероятностью того, что все записи попадут в одну стопку. И то, и другое может произойти. Поэтому реализация на массивах приведет к выделению места дополнительно под 10N записей для числовых ключей, 26N записей для буквенных ключей, причем это место еще увеличивается, если в ключ могут входить произвольные символы или в буквенных ключах учитывается регистр. Кроме того, при использовании массивов нам потребуется время на копирование записей в стопки на этапе формирования стопок и на обратное их копирование в список на этапе сборки списка. Это означает, что каждая запись «перемещается» 2М раз. Для длинных записей такое копирование требует значительного времени.
Другой подход состоит в объединении записей в список со ссылками. Тогда, как помещение записи в стопку, так и ее возвращение в список требует лишь изменения ссылки. Требуемая дополнительная память по-прежнему остается значительной, поскольку на каждую ссылку в стандартной реализации уходит от двух до четырех байтов, а значит требуемая дополнительная память составит 2N или 4N байтов.


Думаю, не ошибусь, если промолчу ;)
2 | Автор: Archi | 2008-03-15, 00:06   |  Репутация: [ + 3 ]
Форум ПРОГРАММИСТОВ » ПРОГРАММИРОВАНИЕ » Алгоритмы » Алгоритмы сортировок (Корневая сортировка)
Страница 1 из 11
Поиск: