Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 44
Текст из файла (страница 44)
Глава 8. Сортировка за линейное время 221 8.1 Нижние оценки алгоритмов сортировки В алгоритмах сортировки сравнением для получения информации о расположении элементов входной последовательности (а1, аз,..., а„) используются только попарные сравнения элементов.
Другими словами, для определения взаимного порядка двух элементов а; и а. выполняется одна из проверок сч < а, а; < аэ, а2 = аэ, а; > а или а; > аээ Значения самих элементов или иная информация о них не доступна. В этом разделе без потери общности предполагается, что все входные элементы различны. При этом операция сравнения а2 = а становится бесполезной, и можно предположить, что никаких сравнений этого вида не производится. Заметим также, что операции а, < аэ, а, < а, а2 = аэ, а; > а на; > а эквивалентны в том смысле, что они дают одну и ту же информацию о взаимном расположении элементов а, и а .. Таким образом, можно считать, что все сравнения имеют вид а; < аэ.
Модель дерева решений Абстрактное рассмотрение алгоритмов сортировки сравнением можно производить с помощью деревьев решений (оес1з1оп 2геез). Дерево решений — это полное бинарное дерево, в котором представлены операции сравнения элементов, производящиеся тем или иным алгоритмом сортировки, который обрабатывает входные данные заданного размера. Управляющие операции, перемещение данных и все другие аспекты алгоритма игнорируются.
На рис. 8.1 показано дерево решений, которое соответствует представленному в разделе 2.1 алгоритму сортировки вставкой, обрабатывающему входную последовательность из трех элементов. В дереве решений каждый внутренний узел обозначен двухиндексной меткой 1 : 2, где индексы 2' и 2 принадлежат интервалу 1 < г,2 < п, а и— это количество элементов во входной последовательности. Метка указывает на 1.2 1 Д'2 1(1,2,321 13 ' 5.1,221 1' 2:~') ~0,2,222 222,1Л! ~Р22,121 8222г121 Рнс. 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 достижимыми листьями, которое соответствует сортировке сравнением п элементов. Поскольку каждая из п1 перестановок входных элементов сопоставляется с одним из листьев, п1 < 1. Так как бинарное дерево высоты 6 имеет не более 2" листьев, получаем: и! < 1 < 2", откуда после логарифмирования в силу монотонности логарифма и уравнения (3.18) следует: Ь > 18(п!) = Й(п18п). Следствие 8.2.
Пирамидальная сортировка и сортировка слиянием — асимптоти- чески оптимальные алгоритмы сортировки. Доказаюиельсюиво. Верхние границы 0(п18п) времени работы пирамидальной сортировки и сортировки слиянием, совпадают с нижней границей Й(п 18 п) для наихудшего случая из теоремы 8.1. Упражнения 8.1-1. Чему равна наименьшая допустимая глубина, на которой находится лист дерева решений сортировки сравнением? 8.1-2.
Получите асимптотически точные границы для величины 18 1п)), не используя приближение Стирлинга. Вместо этого воспользуйтесь для оценки суммы 2 ~ 1 18 Й методом, описанным в разделе А.2. 8.1-3. Покажите, что не существует алгоритмов сортировки сравнением, время работы которых линейно по крайней мере для половины из гй вариантов входных данных длины и. Что можно сказать по поводу 1/и-й части всех вариантов входных данных? По поводу 1/2"-й части? 8.1-4. Производится сортировка последовательности, состоящей из и элементов. Входная последовательность состоит из и/1с подпоследовательностей, в каждой из которых к элементов. Все элементы данной подпоследовательности меньше элементов следующей подпоследовательности и больше элементов предыдущей подпоследовательности.
Таким образом, для сортировки всей п-элементной последовательности достаточно отсортировать Й элементов в каждой из и/)с подпоследовательностей. Покажите, что нижняя граница количества сравнений, необходимых для решения этой разновидности задачи сортировки, равна П (и 18 1с). (Указание: просто скомбинировать нижние границы для отдельных подпоследовательностей недостаточно.) 224 Часть !!. Сортировка и порядковая статистика 8.2 Сортировка подсчетом В сортировке подсчетом (соцпбп8 зог!) предполагается, что все п входных элементов — целые числа, принадлежащие интервалу от О до Гс, где 1с — некоторая целая константа.
Если !с = 0 (и), то время работы алгоритма сортировки подсчетом равно !В (и). Основная идея сортировки подсчетом заключается в том, чтобы для каждого входного элемента х определить количество элементов, которые меньше х. С помощью этой информации элемент х можно разместить на той позиции выходного массива, где он должен находиться. Например, если всего имеется 17 элементов, которые меньше х, то в выходной последовательности элемент х должен занимать ! 8-ю позицию. Если допускается ситуация, когда несколько элементов имеют одно и то же значение, эту схему придется слегка модифицировать, поскольку мы не можем разместить все такие элементы в одной и той же позиции.
При составлении кода для этого алгоритма предполагается, что на вход подается массив А [1..и], так что 1епдгй (А] = и. Потребуются еще два массива: в массиве В (1..и] будет содержаться отсортированная выходная последовательность, а массив С [О..Ц служит временным рабочим хранилищем: Соиыт!ыа Болт(А, В, й) ! 1ог г' — О !о Й 2 до С[1] — О 3 Гог д' — 1 Го 1еидЯА] 4 бо С[АЯ вЂ” С[А[Я] + 1 5 с В С(г] хранится количество элементов, равных 4. 6 Гог г — 1 го !с 7 до С(Г] — С(г] + С[4 — Ц 8 с В СЯ вЂ” количество элементов, не превышающих г. 9 !ог д' — 1епдй[А] дозчпго 1 !о до В[С[А[2]Ц вЂ” А[7! 11 С(А[1Ц вЂ” С[А [7Ц вЂ” 1 Работа алгоритма сортировки подсчетом проиллюстрирована на рис. 8.2.
В части а рисунка показан массив А и вспомогательный массив С после выполнения строки 4. В части б рисунка массив С приведен после выполнения строки 7. В частях в — д показано состояние выходного массива В и вспомогательного массива С после, соответственно, одной, двух и трех итераций цикла в строках 9-11. Заполненными являются только светло-серые элементы массива В. Конечный отсортированный массив В изображен в части е рисунка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
