Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
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-сортировки называется лексикографической сортировкой.
Идея алгоритма очень проста. Создадим для обеспечения работы алгоритма две необходимые структуры данных:
Для простоты изложения рассмотрим случай, когда длина 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).