Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 46
Текст из файла (страница 46)
Управляющие операции, перемещение данных и все другие аспекты алгоритма игнорируются. На рис. ЗЛ показано дерево решений, которое соответствует представленному в разделе 2.1 алгоритму сортировки вставкой, обрабатывающему входную последовательность нз трех элементов. В дереве решений каждый внутренний узел помечен двухиндексной меткой т: т, где индексы т и т принадлежат интервалу 1 < з, т' < п, а и представляет собой количество элементов входной последовательности. Каждый лист также помечен — перестановкой (зг(1), зг(2),..., зг(п)). (Детальный материал по перестановкам содержится в разделе В.1.) Выполнение алгоритма сортировки соответствует прохождению пути от корня дерева до одного нз его листьев. Каждый внутренний узел соответствует выполнению сравнения а; < а .. Левое поддерево после этого сравнения определяет последующие сравнения после того, как мы выяснили, что а; < аз, а правое — в случае а; > а.. Дойдя до какпгонибудь из листьев, алгоритм сортировки устанавливает соответствующее этому листу упорядочение элементов а (и < а (2) « а„(„).
Поскольку каждый корректный алгоритм сортировки должен быть способен произвести любую пе- Часть 11 Сортировка и порядковая статистика 222 рестановку входных элементов, необходимое условие корректности сортировки сравнением заключается в том, что в листьях дерева решений должны размещаться все и! перестановок и элементов и что из корня дерева к каждому его листу можно проложить путь, соответствующий одному из реальных вариантов работы сортировки сравнением. (Назовем такие листы достижимыми.) Таким образом, мы будем рассматривать только такие деревья решений, в которых каждая из перестановок представлена в виде достижимого листа.
Нижняя граница в наихудшем случае Длина самого длинного пути от корня дерева решений к любому из его достижимых листьев соответствует количеству сравнений, которые выполняются в рассматриваемом алгоритме сортировки в наихудшем случае. Следовательно, количество сравнений, выполняемых в том или ином алгоритме сортировки сравнением в наихудшем случае, равно высоте его дерева решений. Поэтому нижняя граница высот для всех деревьев, в которых все перестановки представлены достижимыми листьями, является нижней оценкой времени работы для любого алгоритма сортировки сравнением.
Эту оценку дает приведенная ниже теорема. Теорема 8.1 Любой алгоритм сортировки сравнением в наихудшем случае требует выполнения Й(и 18 и) сравнений. Доказательство. Из приведенных выше рассуждений понятно, что для доказательства теоремы достаточно определить высоту дерева, в котором каждая перестановка представлена достижимым листом. Рассмотрим дерево решений высотой !т с 1 достижимыми листьями, которое соответствует сортировке сравнением и элементов.
Поскольку каждая из и'. перестановок входных элементов сопоставляется с одним из листьев, и! < 1. Так как бинарное дерево высотой 6 имеет не более 2" листьев, имеем и~ < 1 < 2л откуда после логарифмирования следует Ь > 18(и!) (поскольку 18 — строго возрастающая функция) = Й(и 18 и) (согласно уравнению (3.19)) . Следствие 8.2 Пирамидальная сортировка и сортировка слиянием являются асимптотически оп- тимальными сортировками сравнением.
Доказательство. Верхние границы 0(и 18 и) времени работы пирамидальной сортировки и сортировки слиянием совпадают с нижней границей Й(и !к и) для наихудшего случая из теоремы 8.1. ггз Глава 8. Сортировка эа яииейиое врвив Упражнения 8.1.1 Чему равна наименьшая возможная глубина, на которой находится лист дерева решений сортировки сравнением? 8.1.2 Получите асимптотически точные границы для величины 18(п!), не используя приближение Стирлинга. Вместо этого воспользуйтесь для оценки суммы 2.", 1я й методами из раздела А.2. 8.1.3 Покажите, что не существует алгоритмов сортировки сравнением, время работы которых линейно по крайней мере для половины из и! вариантов входных данных длиной и.
Что можно сказать по поводу 1/и-й части всех вариантов входных данных длиной и? По повсду 1/2"-й части? 8.1.4 Предположим, что у вас имеется последовательность, состоящая из и элементов. Входная последовательность состоит из и/и подпоследовательностей, в каждой из которых )с элементов. Все элементы данной подпоследовательности меньше элементов следующей подпоследовательности и больше элементов предыдущей подпоследовательности.
Таким образом, для сортировки всей и-элементной последовательности достаточно отсортировать !е элементов в каждой из и/й подпоследовательностей. Покажите, что нижняя граница количества сравнений, необходимых для решения этой разновидности задачи сортировки, равна Й(п!йй). (Указаниеэ просто скомбинировать нижние границы для отдельных подпоследовательностей недостаточно.) 8.2. Сортировка подсчетом В сортировке подсчетам (совлбпй аоП) предполагается, что каждый из и входных элементов — целое число, принадлежащее интервалу от 0 до к, где ив некоторая целая константа. Если и = 0(п), то время работы алгоритма сортировки подсчетом равно 9(п). Основная идея сортировки подсчетом заключается в том, чтобы для каждого входного элемента х определить количество элементов, которые меньше к.
С помощью этой информации элемент х можно разместить в той позиции выходного массива, где он должен находиться. Например, если всего имеется 17 элементов, которые меньше х, то в выходной последовательности элемент к должен занимать 18-ю позицию. Если возможна ситуация, когда несколько элементов имеют одно и то же значение, зту схему нужно слегка модифицировать, поскольку все такие элементы не могут размещаться в одной и той же позиции. Часть Рл Сортировка и иоридкотт статистика 224 В коде сортировки подсчетом предполагается, что входные данные представляют собой массив А(1.. и], и, таким образом, А.1епд!Ь = п.
Требуются также два дополнительных массива: массив В[1 .. и( хранит отсортированные выходные данные, а массив С[0 .. Гс] предоставляет временное рабочее пространство. Сопнтпяп-Яокт(А, В, !с) ! Пусть С(0., й] — новый массив 2 !ог г' = 0 то lс 3 С[1]=0 4 !ог !' = 1 Го А.!епдй 5 С[А[2]] = С[А[7]] + 1 6 // Сейчас С[1] содержит количество элементов, равных 1. 7 Гог1 = 1 Го й 8 С[!] = С[1]+С[1 — 1] 9 // Сейчас С[1] содержит количество элементов, не превышающих г.
!О Гог 2 = А.1епд!!в с)оивпго 1 11 В[С[А[2]]] = А[2] !2 С(А(2]] = С(А[Д вЂ” 1 Работа алгоритма сортировки подсчетом проиллюстрирована на рис.8.2. После того как в цикле Гог в строках 2 и 3 массив С инициализирован нулевыми значениями, цикл !ог в строках 4 и 5 просматривает каждый входной элемент. Если значение входного элемента равно в, мы увеличиваем С(1]. Таким образом, после строки 5 элемент С(1] содержит количество входных элементов, равных г, для каждого целого значения 1 = 0,1,..., !с. В строках 7 и 8 для каясдого ! = О, 1,..., Г путем суммирования элементов массива С определяется, сколько входных элементов не превышают Г, Наконец в цикле Гог в строках 10 — 12 каждый элемент А[2] помещается в надлежашую позицию выходного массива В.
Если все и элементов различны, то при первом переходе к строке 10 для каждого элемента А(2] в переменной С(А[Д хранится корректный индекс конечного положения этого элемента в выходном массиве, поскольку имеется С[А[2]] элементов, меньших или равных А(2]. Поскольку разные элементы могут иметь одни и те же значения, помещая значение А[2] в массив В, мы каждый раз уменьшаем С[А(Д на единицу.
Благодаря этому следующий входной элемент, значение которого равно А(2] !если таковой имеется), в выходном массиве размещается непосредственно перед элементом А(2]. Сколько времени требуется для сортировки методом подсчета? Цикл !ог в строках 2 и 3 выполняется за время кэ(!с), цикл Гог в строках 4 и 5 выполняется за время Г3[п), цикл Гог в строках 7 и 8 выполняется за время В(!с) и цикл Гог в строках 10 — ! 2 выполняется за время В(п).
Таким образом, общее время составляет 6(!с+ п). На практике обычно сортировка подсчетом применяется, когда !с = 0(п), и в этом случае общее время работы равно 9(п). Сортировка подсчетом превосходит нижнюю границу П(п!8п), доказанную в разделе 8. 1, поскольку не является сортировкой сравнением. Фактически нигде в коде не производится сравнение входных элементов. Вместо этого непосред- Глана В. Сортировка за лиивйкон время 225 ! 2 3 4 5 б 7 В ! 2 3 4 5 6 7 В А [72'..32 ( 3 [ (3„',2!Л:~В ~:,:~! О ! 2 3 4 5 С [2"[':э !'8 [:7)[;.уз[':78~~ О ! 2 3 4 5 с '.
[О!."-".:Зе[[бе'~ ), О ! 2 3 4 5 с (2'['2.')-л '['б'[""; 8! (е) (в) (6) ! 2 3 4 5 6 7 В 1 2 3 4 5 6 7 В 1 2 3 4 5 6 7 В в ~С ["Е([."О ';2 х.'.З'.~~'-".3 ', О 1 2 3 4 5 с ) ! ! 71418 ! 7! $',' О ! 2 3 4 5 с [(г71'4 ['л' 55,), 57~~ (г) (е) (л) Рис. 8.2. Работа алгоритма Сон нтгно-йоит с входным массивом А[1 .. 8], гдс кая!дый элемент А прсдставляст собой нсотрицатсльнос целое число, нс прсвыааюлхсс Ь = б. (а) Массив А и вспомогатсльный массив С после строки 5. (8) Массив С после строки 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
