Структуры данных и алгоритмы (1021739), страница 65
Текст из файла (страница 65)
Тогда цикл в строках (2), (3) листинга 8.13 выполняется за время O(Sj), где st — число различных значений типа tt.Цикл строк (4), (5) требует времени порядка О(п), цикл строк (6), (7) — O(s().Таким образом, общее время выполнения поразрядной сортировки составит£* jO(Sj + п), т.е. O(kn + £ (=1 s ( ), или, если k константа, О(п + 2, j=l s f ).Пример 8.7. Если ключи являются целыми числами из интервала от 0 до л* - 1для некоторой константы k, то можно обобщить пример 8.6 и рассматривать ключикак целые числа по основанию п, состоящие из не более чем k "цифр".
Тогда для8.5. "КАРМАННАЯ" СОРТИРОВКА253всех i, 1 < i < k, ti — целые числа из интервала от О до п - 1 и st = п. В этом случаевыражение О(л + £*=1«() примет вид О(п + kn), которое имеет порядок О(п), поскольку k — константа.Другой пример: если ключи являются символьными строками фиксированнойдлины k, тогда для всех i St = 128 (например) и 5^,=1в( также будет константой.
Таким образом, алгоритм поразрядной сортировки по символьным строкам фиксированной длины выполняется за время О(п). Фактически, если k — константа и все s/являются константами (или если даже имеют порядок роста О(п)), то в этом случаепоразрядная сортировка выполняется за время порядка О(п). Но если k растет вместес ростом п, то время выполнения поразрядной сортировки может отличаться от О(п).Например, если ключи являются двоичными числами длины log га, тогда А = log п иSi = 2 для всех i.
В таком случае время выполнения алгоритма составит О(п logn).1 П- , >-..,.'8.6. Время выполнения сортировок сравнениямиСуществует "общеизвестная теорема" (из математического фольклора), что длясортировки п элементов "требуется времени п logn". Как мы видели в предыдущемразделе, это утверждение не всегда верно: если тип ключей такой, что значенияключей выбираются из конечного (по количеству элементов) множества (это позволяет с "пользой" применить метод "карманной" или поразрядной сортировки), тогдадля сортировки достаточно времени порядка О(га). Однако в общем случае мы не можем утверждать, что ключи принимают значения из конечного множества.
Поэтомупри проведении сортировки мы можем опираться только на операцию сравнениядвух значений ключей, в результате которой можно сказать, что одно ключевое значение меньше другого.Читатель может заметить, что во всех алгоритмах сортировки, которые мы рассмотрели до раздела 8.5, истинный порядок элементов определялся с помощью последовательных сравнений значений двух ключей, затем, в зависимости от результата сравнения, выполнение алгоритма шло по одному из двух возможных путей.В противоположность этому, алгоритм, подобный показанному в примере 8.5, заодин шаг распределяет п элементов с целочисленными значениями ключей по п"карманам", причем номер "кармана" определяется значением ключа.
Все программы раздела 8.5 используют мощное средство (по сравнению с простым сравнением значений) языков программирования, позволяющее за один шаг находить вмассиве по индексу местоположение нужной ячейки. Но это мощное средство невозможно применить, если тип данных ключей соответствует, например, действительным числам.
J3 языке Pascal и в большинстве других языков программирования нельзя объявить индексы массива как действительные числа. И если даже мысможем это сделать, то операцию конкатенации "карманов", номера которых являются машинно-представимыми действительными числами, невозможно будетвыполнить за приемлемое время.Деревья решенийСосредоточим свое внимание на алгоритмах сортировки, которые в процессе сортировки используют только сравнения значений двух ключей. Можно нарисоватьдвоичное дерево, в котором узлы будут соответствовать "состоянию" программы после определенного количества сделанных сравнений ключей.
Узлы дерева можно1Но в этом случае, если двоичные числа длины logra можно трактовать как одно слово,лучше объединить поля ключей в одно поле типа 1..и и использовать обычную "карманную"сортировку.254ГЛАВА 8. СОРТИРОВКАтакже рассматривать как соответствие некоторым начальным упорядочиваниям данных, которые "привели" программу сортировки к такому "состоянию". Можно такжесказать, что данное программное "состояние" соответствует нашим знаниям о первоначальном упорядочивании исходных данных, которые можно получить на данномэтапе выполнения программы.Если какой-либо узел соответствует нескольким упорядочиваниям исходныхданных, то программа на этом этапе не может точно определить истинный порядокданных и поэтому необходимо выполнить следующее сравнение ключей, например"является ли ki < fe2?". В зависимости от возможных ответов на этот вопрос создаются два сына этого узла. Левый сын соответствует случаю, когда значения ключей удовлетворяют неравенству ftt < k2; правый сын соответствует упорядочению1при выполнении неравенства ki > k2.
Таким образом, каждый сын "содержит"информацию, доступную родителю, плюс сведения, вытекающие из ответа на вопрос, "является ли ki < k27".Пример 8.8. Рассмотрим алгоритм сортировки вставками при п = 3. Предположим, что элементы А[1], А[2] и А[3] имеют значения ключей а, Ь и с соответственно. Три элемента, а, б и с можно упорядочить шестью различными способами, поэтому дерево решений начнем строить с узла, представляющего все возможныеупорядочивания и помеченного на рис.
8.5 цифрой (1). Алгоритм сортировкивставками сначала сравнивает значения ключей элементов А[1] и А[2], т.е. сравни2вает значения а и Ь. Если Ь меньше а, то возможны только три правильных упорядочивания Ьас, Ьса и cba, где Ь предшествует а. Эти три упорядочивания соответствуют узлу (2) на рис. 8.5. Другие три упорядочивания (если а меньше Ь, т.е. апредшествует Ь) соответствуют узлу (3), правому сыну узла (1).Теперь посмотрим, что делать дальше, если исходные данные таковы, что в процессе сортировки мы достигли узла (2). Алгоритм сортировки вставками поменяетместами элементы А[1] и А[2], после чего получим текущее упорядочение Ьас. Далеепроводится сравнениэ элементов А[3] и А[2].
Так как теперь А[2] содержит элемент сключом а, то сравниваются ключи а и с. Узел (4) соответствует двум упорядочиваниям из узла (2), когда значение с предшествует значению а, узел (5) соответствуетслучаю, когда а меньше с.Если алгоритм достиг узла (5), то сортировка заканчивается, поскольку этому узлу соответствует одно упорядочивание элементов Ьас. Если алгоритм находится в"состоянии" узла (4), т.е. неравенство А[3] < А[2] истинно, тогда эти элементы переставляются местами: получаем текущее упорядочение Ьса. Далее сравниваются А[1]и А[2], т.е.
значения ключей с и Ь. Узлы (8), (9) соответствуют двум возможным вариантам отношения между значениями с и Ъ. Если состояние программы соответствует узлу (8), то опять переставляются элементы А[1] и А[2]. В каком бы из узлов ((8)или (9)) ни находилась программа сортировки, ее выполнение заканчивается, так какэтим узлам (точнее, листьям дерева решений) соответствуют по одному упорядочению элементов.Поддерево, исходящее из узла (3), полностью симметрично рассмотренному намиподдереву, исходящему из узла (2), поэтому его описание мы опускаем. Дерево решений, показанное на рис.
8.5, позволяет найти правильный порядок расположениязаписей, соответствующий значениям ключей а, Ь я с, поскольку все его листья соответствуют какому-либо одному упорядочению. П1Можно предполагать, что значения всех ключей различны, поскольку если мы можемсортировать элементы с различными ключами, то, несомненно, сможем упорядочить элементыи с совпадающими ключами.2Здесь а, Ь и с не "буквы", а буквенное обозначение значений ключей. Поэтому можетбыть а < Ь и Ь < а.
— Прим. ред.*8.6. ВРЕМЯ ВЫПОЛНЕНИЯ СОРТИРОВОК СРАВНЕНИЯМИ255оabcacbbacbcacabcbaРис. 8.5. Дерево решений для алгоритма сортировки вставкамиРазмер дерева решенийДерево на рис. 8.5 имеет шесть листьев, соответствующих шести возможным упорядочениям исходного списка из трех элементов а, & и с.
В общем случае, если сортируется список из п элементов, тогда существует п! = 1-2-...-(п - 2)-(п - 1)-и возможных исходов, которые соответствуют различным упорядочениям исходного спискаэлементов OL 02, ..., а„. В самом деле, на первую позицию можно поставить любой изп элементов, на вторую — любой из оставшихся п - 1 элементов, на третью — любойиз п - 2 элементов и т.д., произведение количества всех этих частных исходов даетп\. Таким образом, любое дерево решений, описывающее алгоритм сортировки списка из п элементов, должно иметь не менее га! листьев. Фактически, если удалить узлы и листья, соответствующие невозможным сочетаниям элементов, получим в точности л! листьев.Двоичные деревья, имеющие много листьев, должны иметь и длинные пути.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
