Алгоритмы - построение и анализ (1021735), страница 43
Текст из файла (страница 43)
Поскольку каждая из п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. Заполненными являются только светло-серые элементы массива В.
Конечный отсортированный массив В изображен в части е рисунка. После инициализации в цикле Гог в строках 1-2, в цикле Гог в строках 3-4 выполняется проверка каждого входного элемента. Если его значение равно г, то к величине С (г] прибавляется единица. Таким образом, после выполнения стро- Глава 8. Сортировка за линейное время 225 3 4 5 0 7 5 0 ! 2 3 4 5 7 , ']! 0 [ 7 [ [ !7! Ц 4 е,' 5 ' ~"»:1 '1'.:~ "1! '$:"'й " 1415 0 ! 1 3 4 0 ! 2 ! 4 ! 7 ! 2 ~ 4 ! 7 ) 7 1 К ~ 2 3 4 0 Ь 7 5 к ~~ф~~ 0 Гьф~~~фФффЯ 3 у,~~ 2340'0 К ~~ 0 $!Я:::3~~~-~~ 3 ' 3 )~~~ 0 ! 7 3 4 5 е 0 ! ".
3 4 г!)!3!4,517,5! т;» -;1 г) е) а) Рис. 8.2. Обработка алгоритмом Со))итого 8окт входного массива А [1..8], каждый элемент которого — неотрицательное целое число, нс превышающее 5 ки 4 для каждого 4 = О, 1,..., й в переменной С [4] хранится количество входных элементов, равных 4. В строках 6-7 для каждого г = О, 1,..., /с определяется число входных элементов, не превышающих г.
Наконец, в цикле Рог в строках 9-11 каждый элемент А [7] помещается в надлежащую позицию выходного массива В. Если все п элементов различны, то при первом переходе к строке 9 для каждого элемента А [Я в переменной С [А [7]] хранится корректный индекс конечного положения этого элемента в выходном массиве, поскольку имеется С [А [7']] элементов, меньших или равных А [7]. Поскольку разные элементы могут иметь одни и те же значения, помещая значение А [7] в массив В, мы каждый раз уменьшаем С [А [7]] на единицу. Благодаря этому следующий входной элемент, значение которого равно А [5] (если таковой имеется), в выходном массиве размещается непосредственно перед элементом А [7].
Сколько времени требуется для сортировки методом подсчета? На выполнение цикла аког в строках 1-2 затрачивается время 6170), на выполнение цикла аког в строках 3-4 — время О (73), цикл в строках 6-7 требует Е)170) времени, а цикл в строках 9-11 — О (74). Таким образом, полное время можно записать как О 1)с + ге). На практике сортировка подсчетом применяется, когда й = О (ге), а в этом случае время работы алгоритма равно О (73).
В алгоритме сортировки подсчетом нижняя граница П 174 18 74), о которой шла речь в разделе 8.1, оказывается превзойденной, поскольку описанный алгоритм не основан на сравнениях. Фактически нигде в коде не производится сравнение входных элементов — вместо этого непосредственно используются их значения, с помощью которых элементам сопоставляются конкретные индексы.
Нижняя же граница Й (и 1874) справедлива только при выполнении сортировки сравнением. Часть 1!. Сортировка и порядковая статистика 226 Важное свойство алгоритма сортировки подсчетом заключается в том, что ои устойчив (зСаЫе): элементы с одним и тем же значением находятся в выходном массиве в том же порядке, что и во входном. Обычно свойство устойчивости важно только в ситуации, когда вместе сортируемые элементы имеют сопутствующие данные. Устойчивость, присущая сортировке подсчетом, важна еще и по другой причине: этот алгоритм часто используется в качестве подпрограммы при поразрядной сортировке. Как вы увидите в следующем разделе, устойчивость сортировки подсчетом критична для корректной работы поразрядной сортировки.
Упражнения 8.2-1. Используя в качестве модели рис. 8.2, проиллюстрируйте обработку массива А = (6,0,2,0,1,3,4,6,1,3,2) процедурой Ссклчтпчп Яокт. 8.2-2. Докажите, что процедура Сослчтлчо Зонт устойчива. 8.2-3. Предположим, что заголовок цикла сог (строка 9) в процедуре Ссялчтйч0 ЗОнт переписан в таком виде: 9 сог с — 1 Со 1епдйс(А) Покажите, что алгоритм по-прежнему работает корректно. Устойчив ли модифицированный таким образом алгоритм? 8.2-4. Опишите алгоритм, в котором производится предварительная обработка и элементов, принадлежащих интервалу от 0 до )с, после чего в течение времени О (1) можно получить ответ на запрос о том, сколько входных элементов принадлежат отрезку 1а..б].
На предварительную обработку должно использоваться 9 (п + Й) времени. 8.3 Поразрядная сортировка Поразрядная сорнсирояна (гасах зогС) — это алгоритм, который использовался в машинах, предназначенных для сортировки перфокарт. Такие машины теперь можно найти разве что в музеях вычислительной техники. Перфокарты были разбиты на 80 столбцов, в каждом из которых на одной из 12 позиций можно было сделать отверстие. Сортировщик можно было механически "запрограммировать" таким образом, чтобы он проверял заданный столбец в каждой перфокарте, которая находится в колоде, и распределял перфокарты по 12 приемникам в зависимости от того, в какой позиции есть отверстие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
