Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 43
Текст из файла (страница 43)
Быстрая сортировка 217 а) Докажите, что если и = 1епдй [А], то процедура Зтооон бокт(А,1, 1епдгй [А]) корректно сортирует входной массив А [1..п]. б) Запишите рекуррентное соотношение для времени работы процедуры Зтооое Зокт и дайте точную асимптотическую границу (в О- обозначениях) этой величины. в) Сравните время работы процедуры Зтооон Зонт в наихудшем случае со временем сортировки вставкой, сортировки слиянием, пирамидальной сортировки и быстрой сортировки.
Достойны ли эти профессора своих званий? 7-4. Глубина стека дли быстрой сортировки В описанном в разделе 7.1 алгоритме Оглскзокт содержатся два рекурсивных вызова этого же алгоритма. После вызова процедуры Рлкптюн полученные в результате правый и левый подмассивы рекурсивно сортируются. Второй рекурсивный вызов процедуры Яо1скзокт на самом деле не является необходимым; его можно избежать с помощью итеративной управляющей структуры.
Этот метод, получивший название оконечной рекурсии (1а(! геспгз1оп), автоматически обеспечивается хорошими компиляторами. Рассмотрите приведенную ниже версию быстрой сортировки, в которой имитируется оконечная рекурсия: Яглскзокт'(А,р,г) 1 зтййер(т 2 бо ~> Разбиение и сортировка левого подмассива 3 д — Рлкт~т1ом(А, р, г) 4 Оо1скзокт'(А, р, д — 1) 5 р< — я+ 1 а) Докажите, что процедура Оо1скзокт'(А,1, 1епдЮ [А]) корректно сортирует входной массив А. Обычно компиляторы выполняют рекурсивные процедуры с помощью стека, содержащего необходимую информацию, в том числе и значения параметров, применяющихся для каждого рекурсивного вызова.
Информация о самом последнем вызове находится на верху стека, а информация о начальном вызове — на его дне. При вызове процедуры информация записывается в стек (роялей), а при ее завершении — выталкивается (рорреб) из него. Поскольку предполагается, что массивы-параметры представлены указателями, при каждом обращении процедуры к стеку передается информация объемом О (1). Глубина стека (з1аск бербз)— это максимальная величина стекового пространства, которая используется в ходе вычисления. Часть 11. Сортировка и порядковая статистика 218 6) Опишите сценарий, в котором глубина стека, необходимая для обработки процедурой Оглскзокт' п-элементного массива, равна 9 (и). в) Модифицируйте код процедуры Оглскзокт' так, чтобы необходимая для ее работы глубина стека в наихудшем случае была равна О (1йп).
Математическое ожидание времени работы алгоритма О (п 18 и) должно при этом остаться неизменным. 7-5. Разбиение по медиане трех элементов Один из способов улучшения процедуры КАмоом~хвоЯглскзокт заключается в том, чтобы производить разбиение по опорному элементу, определенному аккуратнее, чем путем случайного выбора. Один из распространенных подходов — метод медианы трех элементов (ше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п) к ним не применима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
