5.7. Сортировка с вычисляемыми адресами

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

В качестве примера рассмотрим частный случай сортировки элементов последовательности равных соответственно 6, 3, 5, 7, 2, 4, 1 — различные целые числа от 1 до 7. Значение каждого элемента а, показывает его место в сортированном списке где определяются в цикле

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

Сортировка стала возможной благодаря тому, что значения исходных данных 6, 3, 5, 7, 2, 4, 1 заполняют сплошной интервал последовательности натуральных чисел. Рассмотрим обобщение идеи сортировки с вычисляемыми адресами на случай произвольных целых Алгоритм сортировки существенно упрощается, если все значения различные.

Значения ... различные

Реализация метода сортировки представлена в алгоритме 5.9. Временный массив где используется для сортированной упаковки элементов Свободные места в массиве инициализируются значением отличным от значений элементов

Алгоритм 5.9. Сортировка с вычисляемыми адресами для различных

(см. скан)

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

Алгоритм не содержит вложенных циклов, а значит, сложность его линейная

Допускаются одинаковые значения среди ...

Реализация метода представлена в алгоритме 5.10. Наличие одинаковых элементов среди например, при упаковке ведет к потере данных в исходном множестве Ситуация, когда одновременно несколько элементов претендуют на одно место, называется коллизией. Такие элементы необходимо переразмещать на свободные места, сохраняя свойства сортировки с вычисляемыми адресами. С этой целью на основании величин рассчитывается вектор индексов сортированной упаковки данных в массиве В алгоритме 5.9 роль индексов упаковки могли выполнять непосредственно сами значения элементов так как они были различные. В данном случае значения настраиваются таким образом, что одинаковые по величине элементы из оказываются смежными при их упаковке в массиве Вектор используется для подсчета количества элементов каждого значения среди и формирования индексов упаковки

Алгоритм 5.10. Сортировка с вычисляемыми адресами для произвольных

(см. скан)

(см. скан)

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

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