Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 45
Текст из файла (страница 45)
Рассмотрите приведенную ниже версию быстрой сортировки, в которой имитируется оконечная рекурсия. д. Покажите с помощью границ из (7.7), что решение рекуррентного соотношения (7.6) имеет вид Е [Т(п)] = ез(п1кп). (Указание: с помощью подстановки покажите, что Е [Т(п)] < оп1кп для достаточно больших п и некоторой положительной константы а.) 2!7 Гоово 7. оысероя сортировка ТЛП;Кд СОК ШЧН-Я 01 СКЗодт (А, р, г) 1 иййер < г 2 // Разбиение и сортировка левого подмассива 3 с = Рлкт~тюн(А, р, г) 4 Тлп.-КеспкБ!ЧЕ-(ПлскБОКТ(А,р,д — 1) 5 р= д+1 а Докажите, что Тлп=Кнспкячн-(;Нлскзокт(А, 1, А.
1епд16) корректно сортируег массив А. Обычно компиляторы выполняют рекурсивные процедуры с помощью стека, содержащего необходимую информацию, в том числе и значения параметров, применяющихся для каждого рекурсивного вызова. Информация о последнем вызове находится на вершине стека, а информация о начальном вызове — на его дне. При вызове процедуры информация заносится в стек (рцзЬеб), а при ее завершении — выталкивается (рорред) из него. Поскольку предполагается, что массивы-параметры представлены указателями, при каждом обращении процедуры к стеку передается информация объемом О(1). Глубина стека (з1аск бер1п)— зто максимальная величина стекового пространства, которая используется в ходе вычисления.
б. Опишите сценарий, в котором глубина стека, необходимая для сортировки процедурой Тлш-Кнспкз1чк-О01скзокт п-элементного массива, равна 6(п). в. Модифицируйте код процедуры Тл1с-Ккспкз1чк-Ягпскз0кт так, чтобы необходимая для ее работы глубина стека в наихудшем случае была равна 6(1я и). Математическое ожидание времени работы алгоритма 0(п 1я и) должно при этом остаться неизменным. 7.5. Разбиение яв медиане трех элементов Один из способов улучшения процедуры Клн1эом12нп-Я01скзокт заключается в том, чтобы производить разбиение по опорному элементу, определенному аккуратнее, чем путем случайного выбора.
Один из распространенных подходов — метод медианы трех элементов. Согласно этому методу в качестве опорного элемента выбирается медиана (средний элемент) подмножества, составленного из трех случайно выбранных в подмассиве элементов (см. упр. 7.4.6). В этой задаче предполагается, что все элементы входного массива А[1..п] различны н что п > 3. Обозначим отсортированный выходной массив как А'[1 .. и]. Используя метод медианы трех элементов для выбора опорного элемента х, определим р; = Рг (х = А'[1]).
а Приведите точную формулу для величины р, как функции от и и г для 1 = 2, 3„..., и — 1. (Заметим, что рг = р„= О.) б. На сколько увеличится вероятность выбора в массиве А[1 .. и] в качестве опорного элемента медианы х = А'[[(и+ 1)/2]], если используется не обычный Части П. Сортировка и порядковая статистика способ, а метод медианы? Чему равно предельное отношение этих вероятно- стей при и — к оо? в. Будем считать выбор опорного элемента х = А'~г) "удачным", если п/3 < 1 < 2п/3.
На сколько возрастает вероятность удачного выбора в методе медианы по сравнению с обычной реализацией? (Указание: используйте приближение суммы интегралом.) г. Докажите, что при использовании метода медианы трех элементов время работы алгоритма быстрой сортировки, равное П(п!кп), изменится только на постоянный множитель. 7.б. Нечеткая сортировка интервалов Рассмотрим задачу сортировки, в которой отсутствуют точные сведения о значениях чисел. Вместо них для каждого числа на действительной числовой оси задается интервал, которому оно принадлежит. Таким образом, в нашем распоряжении имеется и закрытых интервалов, заданных в виде !а,,6,), где а; < 6ь Задача в том, чтобы произвести нечеткую сортировку (бзхху-зон) этих интервалов, т.е.
получить такую перестановку (гм 1з,,,., 1„) интервалов, чтобы для каждого 7 = 1, 2,..., п можно было найти значениЯ с Е (ач. 69], УдовлетвоРЯющие неравенствам сг < сз « .. сво а Разработайте алгоритм нечеткой сортировки п интервалов. Общая структура предложенного алгоритма должна совпадать со структурой алгоритма, выполняющего быструю сортировку по левым границам интервалов (т.е. по значениям а;). Однако время работы нового алгоритма должно быть улучшена за счет возможностей перекрывающихся интервалов. (По мере увеличения степени перекрытия интервалов задача их нечеткой сортировки все больше упрощается. В представленном алгоритме следует, насколько это возможно, воспользоваться указанным преимушеством.) б.
Докажите, что в общем случае математическое ожидание времени работы рассматриваемого алгоритма равно Н(п 1к п), но если все интервалы перекрываются (т.е. если существует такое значение х, что х Е (а„6,!) для всех 1, то оно равно кд(п). В предложенном алгоритме этот факт ие следует проверять янно; его производительность должна улучшаться естественным образом по мере увеличения степени перекрытия. Заключительные замечания Процедуру быстрой сортировки впервые разработал Хоар (Ноаге) [169]; предложенная им версия описана в задаче 7.1. Представленная в разделе 7.1 процедура Рлктгт!он появилась благодаря Н.
Ломуто (М. Ьопшго). Содержашийся в разделе 7.4 анализ выполнен Авримом Блюмом (Аитип В!шп). Хороший обзор литературы, посвященной особенностям реализации алгоритмов и их влиянию Гяава 7, Быстрая сортировка на производительность, можно нанти у Седжвика (Бег)йеж1с)г) [303) и Бентли [Вепйеу) [42].
Мак-Илрой (МсПгоу) [246) показал, как создать конструкцию, позволяющую получить массив, при обработке которого почти каждая реализация быстрой сортировки будет выполняться в течение времени й(пз). Если реализация рандомизированная, то данная конструкция может создать данный массив на основании информации о том, каким образом в рандомизированном алгоритме быстрой сортировки осуществляется случайный выбор.
Глава 8. Сортировка за линейное время Вы уже познакомились с несколькими алгоритмами, позволяющими выполнить сортировку и чисел за время 0(п 18п). В алгоритмах сортировки слиянием и пирамидальной сортировки эта верхняя граница достигалась в наихудшем случае; в алгоритме быстрой сортировки она достигалась в среднем. Кроме того, для каждого из этих алгоритмов можно создать такую последовательность из п входных чисел, для которой алгоритм будет работать в течение времени 1)(п 18 и). Все упомянутые алгоритмы обладают одним общим свойством: при сортировке используется только сравнение входных элементов.
Назовем такие алгоритмы сортировки соршириакой сравнением (сотрапаоп зопз). Все описанные до настояшего момента алгоритмы сортировки принадлежат к данному типу. В разделе 8.1 будет доказано, что при любой сортировке сравнением для обработки п элементов в наихудшем случае нужно произвести не менее й(п 18п) сравнений. Таким образом, алгоритмы сортировки слиянием и пирамидальной сортировки асимптотически оптимальны, и не существует алгоритмов этого класса, которые бы работали быстрее и время выполнения которых отличалось бы больше, чем на постоянный множитель. В разделах 8,2-8.4 рассматриваются три алгоритма сортировки: сортировка подсчетом (соцпбп8 зогг), поразрядная сортировка (гад)х зогг) и карманная сортировка (Ъцс(гег зогг).
Все эти алгоритмы выполняются в течение времени, линейно зависящего от количества элементов. Вряд ли стоит говорить о том, что в этих алгоритмах для определения правильного порядка элементов применяются операции, отличные от сравнений, а следовательно, нижняя граница Й(п 18 и) к ним не применима. 8.1. Нижние границы для алгоритмов сортировки В алгоритмах сортировки сравнением для получения информации о расположении элементов входной последовательности (аы аз,..., а„) используются только попарные сравнения элементов.
Другими словами, для определения взаимного порядка двух элементов а, и а выполняется одна из проверок а, < аэ, сч ( а,. а, = а, ьц > ау или а, > а . Значения самих элементов или иная информация о них не доступна никаким иным способом. 221 Главе й Сорглировяа за лилейлое время ф,26)', '1зз ' 6(2,1'';32) ~~ 21зм) ((1(ззз)) ~',3.'1;2)з ((т,'й 1); ((3:Кф Рнс.
8.1. Дерево решений для сортировки вставкой трех элементов. Внутренний узел, помеченный как йу, указывает сравнение мшкду а, н а,. Лист, помеченный перестановкой (л(1), л(2), ..., л(п)), указывает угюрядочение а пз < о 1зз « . а мн Выделенный путь указывает решения, принятые при сортировке входной последовпельности (аз = 6, аз = б, оз = 6); перестановка (3, 1,2) в листе указывает, что отсортированным упорядочением валяется аз = 5 < аз = 6 < аз = 8. Всего имеется 3! = б возможных перестановок входных элементов, так что дерево решений должно иметь как минимум б листьев.
В этом разделе без потери общности предполагается, что все входные элементы различны. При этом операция сравнения а; = аз становится бесполезной, так что можно считать, что никаких сравнений этого вида не производится. Заметим таКжЕ, ЧтООПЕРаЦнназ < а;, аз > а,а; > аз И а; < аз ЭКВИВапситНЫВтОМ СМЫС- ле, что они дают одну и ту же информацию о взаимном расположении элементов а; н а . Таким образом, можно считать, что все сравнения имеют вид а; < а . Модель дерева решений Абстрактное рассмотрение алгоритмов сортировки сравнением можно производить с помощью деревьев решений (бес)я(оп пеев). Дерево решений — зто полное бинарное дерево, в котором представлены операции сравнения элементов, производящиеся тем или иным алгоритмом сортировки, который обрабатывает входные данные заданного размера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
