Зададим d вспомогательных массивов
Работа добавлена на сайт samzan.net:
34.
Распределяющая сортировка
Поразрядная сортировка
Пусть задана последовательность k, состоящая из n ключей. Для изложения принципов работы алгоритмов в дальнейшем будем представлять ключи в виде некоторых чисел в системе счисления с основанием d. В этом случае, как известно, значение каждого разряда лежит в диапазоне от 0 до d – 1. Зададим d вспомогательных массивов. Каждый элемент последовательности k размещаем в массив, номер которого равен значению старшего разряда ключа. Таким образом, все ключи распределятся по массивам, а затем аналогично выполняется сортировка содержимого каждого массива по вторым разрядам ключей и т.д. На рис. 1 приведён пример выполнения первого шага поразрядной сортировки последовательности чисел 964, 135, 564, 731, 111, 130, 952, при этом d = 10. Далее каждый из массивов сортируется по второму разряду и затем уже по третьему – младшему.
Лексикографическая сортировка
Классическим примером LSD-сортировки является лексикографическая сортировка. Прежде, чем описать принцип её работы, определим некоторые необходимые понятия.
Определение 1. Строкой будем называть конечную последовательность s символов из алфавита A и обозначать . Множество всевозможных конечных строк обозначим A*
Определение 2. Будем говорить, что строка Ts=A* меньше строки, если Fp=A*, если
а) либо существует j=<min(s,p) такое, что Ts(i)=Fp(i) для всех i < j, и Ts(j)<Fp(j)
б) либо s < p.
Определение 3. Упорядочивание строк в лексикографическом порядке в соответствии с определением 2 на основе LSD-сортировки называется лексикографической сортировкой.
Идея алгоритма очень проста. Создадим для обеспечения работы алгоритма две необходимые структуры данных:
- для хранения n сортируемых строк рабочую очередь Work;
- массив М размера m, равного мощности алфавита A, элементами которого будут очереди строк.
Для простоты изложения рассмотрим случай, когда длина s сортируемых строк одинакова. Сначала заносим сортируемые строки в очередь Work. В соответствии с алгоритмом LSD-сортировка начинается с последнего s-го символа строки. Просматривая очередь Work, размещаем текущую строку T в очередь M[T(s)], соответствующую s-тому символу текущей строки. После того, как все элементы исходной очереди Work распределятся по очередям массива M, очередь Work станет пустой. Сцепляя очереди массива M в алфавитном порядке, сформируем новую текущую очередь Work, строки которой будут упорядочены по последнему символу. Массив M в этот момент инициализируется нулями. Процесс сортировки продолжается аналогично для (s – 1)-го символа строк и т.д. до первого.
По окончании процесса в очереди Work будут находиться отсортированные в лексикографическом порядке строки. Заметим, что во время сортировки никакие сортируемые элементы не сравнивались между собой, поэтому данная сортировка относится к числу распределяющих. В случае строк различной длины алгоритм принципиально не изменится. Сначала строки упорядочиваются по длинам, для чего создается очередь очередей строк одинаковой длины. В первый момент в рабочую очередь Work размещаются строки максимальной длины, и начинается их сортировка. Как только номер текущего символа совпадает со следующей по значению длиной строки, в начало пустой рабочей очереди размещаются строки, длина которых совпадает с номером текущего символа. Затем посредством конкатенации в Work добавляются очереди массива M.
Что касается реализации алгоритма, то физическое переписывание строк (а они могут быть длинными) из очереди Work в очереди массива M и обратно недопустимо. Воспользуемся тем фактом, что очередь характеризуется двумя указателями на начало и конец . Поэтому массив M можно представить двумерным массивом, содержащим указатели на начало и конец каждой очереди, а сцепление очередей массива M сводится к переопределению этих указателей.
Вычислительная сложность алгоритма
Количество итераций внешнего цикла, обеспечивающего перебор всех символов строки, будет равно числу символов в строке s. Внутри цикла просматриваются все n элементов очереди Work и размещаются в массиве M – это O(n) операций. Далее в том же цикле происходит конкатенация m списков – это ещё O(m) операций. Окончательно получаем, что вычислительная сложность алгоритма равна O(s(n+m)). Очевидно, что если s и m много меньше n, алгоритм будет иметь линейную по n вычислительную сложность. В случае, когда длина строк различна, вычислительную сложность алгоритма можно оценить величиной O(s*+msmax), где s* – суммарная длина всех строк, smax– максимальная длина строки. В случае если smax много меньше n, то оценка будет следующей O(s*+m).
2. е место в мире по добыче и экспорту природного газа35мировой добычи.html
3. СТБ строй Проект рассматриваемый в данной работе предполагает реализацию следующих продуктов- Плито
4. ТАТАРЫ ДЖУНГАРЫ ПРИРОДНЫЕ УСЛОВИЯ СКОТОВОДЧЕСКИЕ КОЧЕВЫЕ
5. тема литературы и страждущий мир.
6. Предмет отрасли права представляет собой совокупность правовых отношений на которые направлено действие
7. Коренной перелом в Великой Отечественной и второй мировой войнах
8. I Этот человек властный порою жестокий но мудрый талантливый беззаветно любящий свое отечество человек
9. Композиционно-семиотический анализ ансамбля Красной площади в Москв
10. это самый крупный из банков развития в мире
11. А 9 І ф Б 9 ПОНЕДІЛоК 1
12. Тема дисципліни. Загальні відомості про мову програмування
13. Основные формы правления в Древнем Риме
14. докладывающих о результатах проверок
15. Скорость высушивания в приборе обеспечивается быстрым прогревом до относительно высоких температур при кр
16. Галицько Волинське князівство
17. не на улице Люкина
18. Загадки Якутии -english-
19. Реферат- Программное обеспечение для создания видеоклипов
20. так больно Но ведь и хорошего в уходящем году тоже было немало1