Главная » Java, Структуры данных и алгоритмы » Поразрядная сортировка

0

Одной из причин необходимости стабильной сортировки является возможность ее применения не только к упорядочению целых чисел. Предположим, необходимо отсортировать объекты пар (к, /), в которых к и / — целые числа в пределах [0, N — 1] для некоторого N>2. Для такой задачи естественно определять порядок этих объектов с помощью лексикографического (словарного) правила, в котором (к\, l\) < (ki, /2) при к\ < к2 или при к\ = ki и 1\ < /2 (п. 7.1.4). Это двухточечная версия лексикографической сравнительной функции, обычно применяемой к символьным строкам одинаковой длины (и легко преобразуемая для кортежей d-чисел при d > 2).

Алгоритм поразрядной сортировки (radix-sort) сортирует последовательность пар S с помощью дважды стабильной сегментной сортировки, вначале применяя в качестве порядкового ключа первый компонент пары, затем второй. Но какой из двух порядков сортировки верный? Следует ли вначале сортировать все к (первые компоненты), а затем все / (вторые компоненты), или же поменять последовательность сортировок? Прежде чем ответить на эти вопросы,-рассмотрим, следующий пример.

Пример 10.2. Рассмотрим следующую последовательность S: S= ((3,3)>(1,5W2,5)>(1,2),(2>3),(1,7),(3,2),(2,2)).

1                                                                    r^

При сортировке по первому компоненту получаем следующую последовательность S\:   ‘

S,= ((1,5),(1,2),(1,7),(2,5),(2,3),(2,2),(3,3),(3,2)).

При сортировке полученной S\ по второму компоненту получаем следующую последовательность S2:

SU2= ((1,2),(2,2),(3,2),(2,3),(3,3),(1,5),(2,5),(1,7)),

которая не является полностью отсортированной. С другой стороны, если вначале отсортировать S по второму компоненту, то получим следующую последовательность:

^2= ((1,2),(3,2),(2,2),(3,3)^(2,3),(1,5),(2,5),(1,7)).

Если теперь S2 отсортировать по первому компоненту, то получим следующую последовательность:      у

S2J = ((1,2),(1,5),(1,7),(2,2),(2,3),(2,5),(3,2),(3,3),

которая в действительности представляет собой лексикографически упорядоченную последовательность S.

Из примера видно, что вначале сортировка должна выполняться по второму, а затем — по первому компоненту. Такой вывод является единственно правильным. При этом порядке сортировки можно гарантировать, что равенство двух элементов при второй сортировке (по первому компоненту) сохранит их относительный порядок после первой сортировки (по второму компоненту). Таким образом, получаемая в результате последовательность всегда будет лексикографически упорядочена. В упражнении М-10.14 дается возможность рассмотреть пример применения такого подхода для объектов из трех и более компонентов. В заключение дадим следующее утверждение.

Утверждение 10.7. Пусть S— последовательность из п пар «ключ-элемент», каждая из которых содержит собственный ключ (к\, к2, …, kj), где ki — целое число в пределах [0, N— 1] при некотором целом числе N>2. С помощью поразрядной сортировки можно лексикографически отсортировать S за 0(d(n + ЛО) времени.

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии