WikiSort.ru - Программирование

Поразрядная сортировка (англ. radix sort) — алгоритм сортировки, который выполняется за линейное время. Существуют стабильные варианты.

Алгоритм

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения. Например, так сортировать можно не только числа, записанные в виде набора цифр, но и строки, являющиеся набором символов, и вообще произвольные значения в памяти, представленные в виде набора байт.

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

Так как выравнивать сравниваемые записи относительно друг друга можно в разную сторону, на практике существуют два варианта этой сортировки. Для чисел они называются в терминах значимости разрядов числа, и получается так: можно выровнять записи чисел в сторону менее значащих цифр (по правой стороне, в сторону единиц, least significant digit, LSD) или более значащих цифр (по левой стороне, со стороны более значащих разрядов, most significant digit, MSD).

При LSD сортировке (сортировке с выравниванием по младшему разряду, направо, к единицам) получается порядок, уместный для чисел. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. То есть, здесь значения сначала сортируются по единицам, затем сортируются по десяткам, сохраняя отсортированность по единицам внутри десятков, затем по сотням, сохраняя отсортированность по десяткам и единицам внутри сотен, и т. п.

При MSD сортировке (с выравниванием в сторону старшего разряда, налево), получается алфавитный порядок, который уместен для сортировки строк текста. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам, приведённым в примере получим последовательность 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Накапливать при каждом проходе сведения о группах можно разными способами — например в списках, в деревьях, в массивах, выписывая в них либо сами элементы, либо их индексы и т. п.

Существует нестабильный вариант рекурсивной побитовой сортировки, выполняющейся непосредственно в сортируемом массиве: на первом проходе движение идёт навстречу друг другу, в начале массива ищется элемент с 1 в первом битовом разряде, в конце массива ищется элемент с 0 в том же разряде. Найденные элементы меняются местами, и так до тех пор, пока рассматриваемые индексы не встретятся. Таким образом в начале массива, до места встречи индексов, собираются все элементы с битом равным 0, а после этого индекса — все элементы с равным 1. Далее рекурсивно можно полностью аналогично перебрать получившиеся поддиапазоны массива, сравнивая значения второго и последующих разрядов, и переставляя элементы местами.

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

Для сортировки по очередному разряду может применяться корзинная сортировка. Каждый разряд проходится по два раза. На первом проходе подсчитывается количество тех или иных значений в этом разряде. Затем для каждого возможного значения подготавливаются массивы для хранения элементов с этим значением. При втором проходе выписываются сами элементы в эти массивы. Эффективная реализация возможна при использовании массива ссылок на строки вместо самих строк, и дополнительного массива «размеров корзин», инициализируемого при первом проходе числом элементов в каждой «корзине».

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

Операция завершается при достижении максимальной длины строки или когда все «подкорзины» получили длину 1.

Реализация (LSD)

 local function list_to_buckets(array, base, iteration)
    local buckets = {}
    for i=0,base-1 do 
        buckets[i]={}
    end
    for _, number in pairs(array) do
        -- определение значения текущего разряда числа
        local digit = math.floor((number / math.pow(base, iteration))) % base
        -- добавить число в контейнер с такими же значениями разряда
        table.insert(buckets[digit],number)
    end
    return buckets
end

local function buckets_to_list(buckets)
    local numbers = {}
    -- добавление в возвращаемый массив из каждого разряда ...
    for _, bucket in pairs(buckets) do
        -- ... каждого числа
        for _, number in pairs(bucket) do
            table.insert(numbers,number)
        end
    end
    return numbers
end

function radix_sort(array, base)
    local base=base or 10
    local maxval = max(array) -- требует реализации max(table)
    local it = 0
    while math.pow(base, it) <= maxval do
        array = buckets_to_list(list_to_buckets(array, base, it))
        it = it + 1
    end
    return array
end

Примечания

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

Литература

• Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 192—201. — ISBN 5-8459-0082-4.

Ссылки

Имеется викиучебник по теме
«Примеры реализации поразрядной сортировки»

• Визуализатор1 — Java-аплет.
• Визуализатор2 — Java-аплет.

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники. Проверить достоверность указанной в статье информации. Перевести текст с иностранного языка на русский.