Алгоритмы - построение и анализ (1021735), страница 42
Текст из файла (страница 42)
Один из распространенных подходов — метод медианы трех элементов (ше61ап- оГ-3). Согласно этому методу, в качестве опорного элемента выбирается медиана (средний элемент) подмножества, составленного из трех выбранных в подмассиве элементов (см. упражнение 7А-6). В этой задаче предполагается, что все элементы входного подмассива А [1..и] различны и что и > 3.
Обозначим сохраняемый выходной массив через А' [1..и]. Используя опорный элемент х с помощью метода медианы трех элементов, определим р; = Рг(х = А' [1]). а) Приведите точную формулу для величины р; как функции от и н 1 для г = 2, 3,..., и — 1. (Заметим, что рг = р„= О.) б) На сколько увеличится вероятность выбора в массиве А [1..п] в качестве опорного элемента х = А' [[(п+ 1)/2]], если используется не обычный способ, а метод медианы? Чему равны предельные значения этих вероятностей при и — со? в) Будем считать выбор опорного элемента х = А' [г] "удачным", если и/3 < 1 < 2п/3.
На сколько возрастает вероятность удачного выбора в методе медианы по сравнению с обычной реализацией? (Указание: используйте приближение суммы интегралом.) г) Докажите, что при использовании метода медианы трех элементов время работы алгоритма быстрой сортировки, равное й (и 18 и), изменится только на постоянный множитель. 7-6. Нечеткая сортировка по интервалам Рассмотрим задачу сортировки, в которой отсутствуют точные сведения о значениях чисел. Вместо них для каждого числа на действительной числовой оси задается интервал, которому оно принадлежит. Таким образом, в нашем распоряжении имеется п закрытых интервалов, заданных в виде [а;,6,], где ги < Ь,.
Задача в том, чтобы произвести нечеткую сортировку (Таге-зоп) этих интервалов, т.е. получить такую 219 Глава 7. быстрая сортировка перестановку ((м 1з,...,1„) интервалов, чтобы в каждом интервале можно было найти значения с е [щ,,б,,1, удовлетворяющие неравенствам с1<сз« .с„. а) Разработайте алгоритм нечеткой сортировки и интервалов. Общая структура предложенного алгоритма должна совпадать со структурой алгоритма, выполняющего быструю сортировку по левым границам интервалов (т.е. по значениям а,). Однако время работы нового алгоритма должно быть улучшено за счет возможностей, предоставляемых перекрытием интервалов. (По мере увеличения степени перекрытия интервалов, задача их нечеткой сортировки все больше упрощается.
В представленном алгоритме следует воспользоваться этим преимуществом, насколько это возможно.) б) Докажите, что в общем случае математическое ожидание времени работы рассматриваемого алгоритма равно О (п18п), но если все интервалы перекрываются (т.е. если существует такое значение к, что длЯ всех 1 т Е [ам Ь,1), то оно Равно О (и). В пРедложенном алгоритме этот факт не следует проверять явным образом; его производительность должна улучшаться естественным образом по мере увеличения степени перекрывания. Заключительные замечания Процедуру быстрой сортировки впервые разработал Хоар (Ноаге) [147); предложенная им версия описана в задаче 7-1.
Представленная в разделе 7.1 процедура Рлкт171сяч появилась благодаря Ломуто (Н. 1.ошшо), Содержащийся в разделе 7.4 анализ выполнен Авримом Блюмом (Ачгпп В!иш). Хороший обзор литературы, посвященной описанию особенностей реализации алгоритмов и их влияния на производительность, можно найти у Седжвика (Бебйеччск) [2681 и Бентли (Веп1!еу) [401. Мак-Илрой (МсПгоу) [216) показал, как создать конструкцию, позволяющую получить массив, при обработке которого почти каждая реализация быстрой сортировки будет выполняться в течение времени О (пз).
Если реализация рандомизированная, то данная конструкция может создать данный массив на основании информации о том, каким образом в рандомизированном алгоритме быстрой сортировки осуществляется случайный выбор. ГЛАВА 8 Сортировка за линейное время Мы уже познакомились с несколькими алгоритмами, позволяющими выполнить сортировку и чисел за время О (и 18 п). В алгоритмах сортировки по методу слияния и пирамидальной сортировки эта верхняя граница достигалась в наихудшем случае; в алгоритме быстрой сортировки она достигалась в среднем случае. Кроме того, для каждого из этих алгоритмов можно создать такую последовательность из п входных чисел, для которой алгоритм будет работать в течение времени й(и!йп). Все упомянутые алгоритмы обладают одним общим свойством: при сортировке нсппэьзуется только сравнение яходньп элементов.
Назовем такие алгоритмы сортировки сортировкой сравнением (согпраг1зоп зоггз). Все описанные до настоящего момента алгоритмы сортировки принадлежат к данному типу. В разделе 8.1 будет доказано, что при любой сортировке путем сравнения для обработки и элементов в наихудшем случае нужно произвести не менее й (и 18 и) сравнений. Таким образом, алгоритмы сортировки слиянием и пирамидальной сортировки асимптотически оптимальны, и не существует алгоритмов этого класса, которые бы работали быстрее и время выполнения которых отличалось бы больше, чем на постоянный множитель.
В разделах 8.2, 8.3 и 8.4 рассматриваются три алгоритма сортировки: сортировка подсчетом (соипбпй зон), поразрядная сортировка (гайх зон) и карманная сортировка (Ьисйе[ зон). Все эти алгоритмы выполняются в течение времени, линейно зависящего от количества элементов. Вряд ли стоит говорить о том, что в этих алгоритмах для определения правильного порядка элементов применяются операции, отличные от сравнений, а следовательно, нижняя граница Й (п18п) к ним не применима. Глава 8. Сортировка за линейное время 221 8.1 Нижние оценки алгоритмов сортировки В алгоритмах сортировки сравнением для получения информации о расположении элементов входной последовательности (аы аз,..., а„) используются только попарные сравнения элементов. Другими словами, для определения взаимного порядка двух элементов а; и а.
выполняется одна из проверок сч < а, а; < а, а; = аэ, а; > а или а; > ау. ЗначениЯ самих элементов или инаЯ инфоРмацим о них не доступна. В этом разделе без потери общности предполагается, что все входные элементы различны. При этом операция сравнения а; = а становится бесполезной, и можно предположить, что никаких сравнений этого вида не производится. Заметим также, что операции а, < а„а, < а, а! = а, а; > а на; > а эквивалентны в том смысле, что они дают одну и ту же информацию о взаимном расположении элементов а, и а .. Таким образом, можно считать, что все сравнения имеют вид а; < ау.
Модель дерева решений Абстрактное рассмотрение алгоритмов сортировки сравнением можно производить с помощью деревьев решений (бес!з!оп !геев). Дерево решений — это полное бинарное дерево, в котором представлены операции сравнения элементов, производящиеся тем или иным алгоритмом сортировки, который обрабатывает входные данные заданного размера. Управляющие операции, перемещение данных и все другие аспекты алгоритма игнорируются. На рис. 8.1 показано дерево решений, которое соответствует представленному в разделе 2.1 алгоритму сортировки вставкой, обрабатывающему входную последовательность из трех элементов. В дереве решений каждый внутренний узел обозначен двухиндексной меткой 1 : т', где индексы с' и ! принадлежат интервалу 1 < г,э' < п, а и— это количество элементов во входной последовательности.
Метка указывает на Рнс. 8.1. Дерево решений лля алгоритма сортировки вставкой, обрабатывающего три элемента Часть 11. Сортировка и порядковая статистика 222 то, что сравниваются элементы а, и а . Каждый лист помечен перестановкой (я (1),гг(2),...,я (гг)), которая представляет окончательное упорядочение элементов (а (И < а 1э) « а 1„1).(Детальный материал по перестановкам содержится в разделе В.1.) Выполнение алгоритма сортировки соответствует прохождению пути от корня дерева до одного из его листьев.
Толстой серой линией на рис. 8.1 выделена последовательность решений, принимаемых алгоритмом при сортировке входной последовательности (аг = 6, аэ = 8, аз = 5); показанная в листе дерева перестановка (3, 1, 2) указывает на то, что порядок сортировки определяется соотношениями аз = 5 < аг = 6 < аэ = 8. В данном случае всего имеется 31 = 6 возможных перестановок входных элементов, поэтому дерево решений должно иметь не менее б листьев.
В общем случае в каждом внутреннем узле производится сравнение сч < а . Левым поддеревом предписываются дальнейшие сравнения, которые нужно выполнить при аг < а, а правым — сравнения, которые нужно выполнить при аг > а . Дойдя до какого-нибудь из листьев, алгоритм сортировки устанавливает соответствующее этому листу упорядочение элементов (а 1И < а„(з) « а 1„1). Поскольку каждый корректный алгоритм сортировки должен быть способен произвести любую перестановку входных элементов, необходимое условие корректности сортировки сравнением заключается в том, что в листьях дерева решений должны размещаться все и. 'перестановок и элементов, и что из корня дерева к каждому его листу можно проложить путь, соответствующий одному из реальных вариантов работы сортировки сравнением.
(Назовем такие листы "достижимыми".) Таким образом, мы будем рассматривать только такие деревья решений, в которых каждая из перестановок представлена в виде достижимого листа. Нижняя оценка для наихудшего случая Величина самого длинного пути от корня дерева решений к любому из его достижимых листов соответствует количеству сравнений, которые выполняются в рассматриваемом алгоритме сортировки в наихудшем случае. Следовательно, количество сравнений, выполняемых в том или ином алгоритме сортировки сравнением в наихудшем случае, равно высоте его дерева решений. Поэтому нижняя оценка высот для всех деревьев, в которых все перестановки представлены достижимыми листьями, является нижней оценкой времени работы для любого алгоритма сортировки сравнением.
Эту оценку дает приведенная ниже теорема. Теорема 8.1. В наихудшем случае в ходе выполнения любого алгоритма сорти- ровки сравнением выполняется Й (и 18 п) сравнений. Доказательство. Из приведенных выше рассуждений становится понятно, что для доказательства теоремы достаточно определить высоту дерева, в котором каждая перестановка представлена достижимым листом. Рассмотрим дерево решений Глава 8. Сортировка за линейное время 223 высотой 6 с 1 достижимыми листьями, которое соответствует сортировке сравнением п элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
