Регистрация


Рубрики


Ссылка на сайт:
Поразрядная координатная сортировка

СБОРНИК НАУЧНЫХ ТРУДОВ НГТУ. – 2009. – № 3(57). – 123–126

УДК 004.021

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

В. О. ИВАНОВ¨

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

ВВЕДЕНИЕ

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

Следует подробнее остановиться на существующих алгоритмах. В [4–6] описан алгоритм поразрядной распределяющей сортировки, заключающийся в делении исходного массива на две части по значению очередного двоичного разряда и слиянию этих частей с выбором наименьшего из текущих элементов промежуточных массивов. Эффективность этого алгоритма прямо пропорциональна произведению количества сортируемых элементов на их максимальную разрядность в двоичной системе исчисления, а выделяемая дополнительно память занимает объем, в два раза больший, чем данные. Здесь же описан алгоритм сортировки разделением по двоичным разрядам. Массив сортируемых значений делится на две части так, что в левой оказываются значения со старшим значащим битом, равным 0, а в правой – со значением 1. Затем обе части массива делятся в свою очередь каждая на две части по значению следующего правого бита и так далее. В результате, когда мы доберемся до младшего бита, массив окажется упорядоченным. Эффективность этого алгоритма такая же, без учёта затрат на перестановки элементов массива. В источниках на сайтах Интернета, указанных в списке литературы (п. 1–3), описаны другие варианты поразрядных сортировок, например сортировка подсчётом и побайтовая сортировка. При анализе их алгоритмов можно увидеть, что количество проходов исходного массива для всех рассмотренных вариантов прямо пропорционально произведению количества элементов на максимальное количество их разрядов, а количество необходимой памяти сравнимо с размером сортируемых данных. Такие показатели скорости выгодно отличают алгоритм от большинства других методов сортировки, но, как далее показано автором этой статьи, далеко не передельны.

Если Вы желаете скачать полную версию статьи, пройдите регистрацию на сайте http://sbornik. infoterra. ru/reg. php

 



Пожаловаться

Материал из рубрики: Мои статьи
5
рейтинг рассчитывается на оценке от 1 до 5