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

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

Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время.

Содержание

Алгоритм

Алгоритм сортировки.
Числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

При MSD сортировке последовательность сортируется по старшему значимому двоичному разряду так, чтобы все ключи начинающиеся с 0 оказались перед всеми ключами начинающимися с 1. Для этого необходимо найти крайний слева ключ K_i, начинающийся с 1, и крайний справа ключ K_j, начинающийся с 0. После чего K_i и K_j меняются местами, и процесс повторяется, пока не получится i > j. Пусть F_0 — множество элементов начинающихся с 0, F_1 — множество всех остальных элементов. Применим к F_0 поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F_0 полностью не рассортируется. Затем проделаем то же самое с F_1.

Применение для строк

Вместо сравнения N-й битовой позиции в слове сравнивается N-й байт строки.

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

N-й (для N > 0) проход выполняется последовательно над каждой корзиной, полученной на (N - 1)-м проходе, с делением её на «подкорзины». В этом проходе сравниваются N-ные символы каждой строки.

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


Литература

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

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Поразрядная сортировка" в других словарях:

  • поразрядная сортировка — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN pocket sorting …   Справочник технического переводчика

  • Сортировка Шелла — (англ. Shell sort)  алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными… …   Википедия

  • Сортировка выбором — (Selection sort)  алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… …   Википедия

  • Сортировка вставками — Сортировка вставками  простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до …   Википедия

  • Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort)  простой алгоритм сортировки. Для понимания и реализации этот алгоритм  простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… …   Википедия

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

  • Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… …   Википедия

  • Сортировка расчёской — (англ. comb sort)  это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine …   Википедия

  • Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п …   Википедия

  • Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»