Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 47
Текст из файла (страница 47)
(в)-(д) Выходной массив В и вспомогательный массив С после одной, двух и трех итераций цикла в строках 10-12 соотвстствснно. Звполнсниымн авллнпся только свбтло-ссрыс элсмснты массива В. (В) Окончатсльный отсортированный выходной массив В. Упражнении 8.2.1 Используя рис.
8.2 в качестве образца, проиллюстрируйте обработку массива А = (6,0,2,0,1,3,4,6,1,3,2) процедурой Со()ытича-Войт. 8.2.2 Докажите, что сортировка Со(дчтичо-Бокт устойчива. о.2.3 Предположим, что заголовок цикла дог (строка 10) в процедуре Со(пчтпчп-Б(зкт переписан в следующем виде: 1О (ог 5' = 1 (о А. (епд()) ственно используются их значения, с помощью которых элементам сопоставляются конкретные индексы. Нижняя граница й(п 18 и) для сортировки сравнением неприменима при отказе от модели сортировки, использующей сравнения.
Важное свойство алгоритма сортировки подсчетом заключается в его устойчцвнсвзц (в(аЫе): элементы с одним и тем же значением находятся в выходном массиве в том же порядке, что и во входном. Обычно свойство устойчивости важно только в ситуации, когда вместе сортируемые элементы имеют сопутствующие данные. Устойчивость, присущая сортировке подсчетом, важна еще и по другой причине: этот алгоритм часто используется в качестве подпрограммы при поразрядной сортировке.
Как вы увидите в следующем разделе, устойчивость сортировки подсчетом критична для корректной работы поразрядной сортировки. Части Рй Сортировка и порядковая статистика Покажите, что алгоритм по-прежнему работает корректно. Устойчив ли модифи- цированный таким образом алгоритм? 8.2.4 Опишите алгоритм предварительной обработки и элементов, принадлежащих интервалу от 0 до 6, после которого можно получить ответ на запрос о том, сколько из и входных элементов принадлежат отрезку 1а ..
6), за время 0(1). Алгоритм должен выполняться за время 9(п + 1с). 8.3. Поразрядная сортировка Поразрядная сортировка (гад(х яоп) — это алгоритм, который использовался в машинах, предназначенных для сортировки перфокарт. Такие машины теперь можно найти разве что в музеях вычислительной техники.
Перфокарты были разбиты на 80 столбцов, в каждом из которых в одной из 12 позиций можно было сделать отверстие. Сортировщик можно было механически "запрограммировать" таким образом, чтобы он проверял заданный столбец в каждой перфокарте, которая находится в колоде, и распределял перфокарты по 12 приемникам в зависимости от того, в какой позиции расположено отверстие. После этого оператор получал возможность извлечь перфокарты из всех приемников и разместить их так, чтобы сверху находились перфокарты с пробитым первым разрядом, за ними — перфокарты с пробитым вторым разрядом и т.д. При записи десятичных цифр в каждом столбце используются лишь первые десять разрядов (остальные два разряда нужны для кодирования символов, отличных от цифр).
Таким образом, число, состоящее из д цифр, занимает поле из с( столбцов. Поскольку сортировшик за один раз может обработать только один столбец, для решения задачи о сортировке п перфокарт в порядке возрастания записанных на них о-значных чисел требуется разработать некий алгоритм сортировки. Интуиция подсказывает способ сортировки, при котором выполняется сортировка по ссларивей цифре, а затем полученные стопки рекурсивно сортируются по следующим в порядке старшинства цифрам.
К сожалению„в этом случае возникает большое количество промежуточных стопок перфокарт (после первой же сортировки по старшей цифре — десять стопок), за которыми нужно следить (см. упр. 8.3.5). В алгоритме поразрядной сортировки поставленная задача решается способом, противоположным подсказываемому интуицией. Сначала производится сортировка по ясладисей цифре, после чего перфокарты снова объединяются в одну колоду, в которой сначала идут перфокарты из нулевого приемника, затем — из первого приемника, затем — из второго и т.д.
После этого вся колода снова сортируется по предпоследней цифре, и перфокарты вновь собираются в одну стопку тем же образом. Процесс продолжается до тех пор, пока перфокарты не окажутся отсортированными по всем с( цифрам. После этого перфокарты оказываются полностью Глава 8.
Сортировка за линейное время 227 720 929 329 355 436 436 839 --Вь 457 355 657 457 720 657 $39 329 720 457 355 657 436 839 --Ви 457 ---а ° 436 657 720 329 355 839 Рнс. 8.3. Поразрядная сортировка списка нз семи трехзначных чисел. В крайнем слева столбце показаны входные числа, а в последующих столбцах — последовательные состояния списка после его сортнровкв по цифрам, начиная с младшей. Серым цветом выделен текущий разряд, по пггорому производится сортировка, в результате чего получается следующий (расположенный справа) столбец. КАО! х-БОкт(А, гг) 1 1огз'=1$од 2 Выполнить устойчивую сортировку массива А по цифре г Лемма В.з Пусгь имеется и г1-значных чисел, в которых каждая цифра принимает одно из к возможных значений.
Тогда алгоритм Кдгнх-Бокт позволяет выполнить коррект- ную сортировку этих чисел за время ез(гг(п + Й)), если устойчивая сортировка, используемая данным алгоритмом, имеет время работы ег(п + 7с). отсортированными в порядке возрастания И-значных чисел. Таким образом, для сортировки перфокарт требуется лишь И проходов колоды. На рис. 8.3 показано, как поразрядная сортировка обрабатывает "колоду" из семи трехзначных чисел. Важно, чтобы сортировка по цифрам того или иного разряда в этом алгоритме обладала устойчивостью.
Сортировка, которая производится сортировшиком перфокарт, устойчива, но оператор должен также следить за тем, чтобы не перепутать порядок перфокарт после извлечения их из приемника. Это важно, несмотря на то что на всех перфокартах из одного и того же приемника в столбце, номер которого соответствует этапу обработки, стоит одна и та же цифра. В типичных компьютерах, представляющих собой машины с произвольным доступом к памяти, поразрядная сортировка иногда применяется для приведения в порядок записей, ключи которых разбиты на несколько полей. Например, пусть нужно выполнить сортировку дат по трем ключам: год, месяц и день.
Для этого можно было бы запустить алгоритм сортировки с функцией сравнения, в котором в двух заданных датах сначала сравнивались бы годы, при их совпадении сравнивались бы месяцы, а при совпадении и тех, и других сравнивались бы дни. Можно поступить и по-другому, т.е, выполнить трехкратную сортировку с помощью устойчивой процедуры: сначала — по дням, затем — по месяцам и наконец— по годам.
Код поразрядной сортировки прост и прямолинеен. В приведенной ниже процедуре предполагается, что каждый из п элементов массива А — это число, в котором всего д цифр, причем первая цифра стоит в самом младшем разряде, а цифра под номером д — в самом старшем разряде. Часть И, Сортировка и лориоковаи статистика Доказательство. Корректность поразрядной сортировки доказывается методом математической индукции по сортируемым столбцам (см.
упр. 8.3.3). Анализ времени работы рассматриваемого алгоритма зависит от того, какой из методов устойчивой сортировки используется в качестве промежуточного алгоритма сортировки. Если каждая цифра принадлежит интервалу от О до Й вЂ” 1 (и, таким образом, может принимать (с возможных значений) и к не слишком велико, то оптимальным выбором является сортировка подсчетом.
Для обработки каждой из Н цифр п чисел понадобится время 9(п + к), а все цифры будут обработаны алгоритмом поразрядной сортировки в течение времени 0(с((п + /с)). Если с1 — константа, а /с = 0(п), то время работы алгоритма поразрядной сортировки линейно зависит от количества входных элементов.
В общем случае мы получаем определенную степень свободы в выборе разбиения ключей на цифры. Лемма 8.4 Пусть имеется и 6-битовых чисел и произвольное натуральное число т < 6. Алгоритм Клех-8Окт позволяет выполнить корректную сортировку этих чисел за время 0((6/т) (и+2')), если используемая им устойчивая сортировка имеет время работы 9(п + 1с) для входных данных в диапазоне от О до /с. Доказательелсво. Для значения т < 6 каждый ключ можно рассматривать как число, состоящее из Н = (Ь/т ~ цифр по т бит, Все цифры представляют собой целые числа в интервале от О до 2' — 1, поэтому можно воспользоваться алгоритмом сортировки подсчетом, в котором 1с = 2' — 1 (например, 32-битовое слово можно рассматривать как число, состоящее из четырех 8-битовых цифр, так что Ь = 32, т = 8, lс = 2" — 1 = 255, а Н = Ь/т = 4).
Каждый проход сортировки подсчетом занимает время 6(п + 1с) = 9(п + 2"), а всего выполняется Ы проходов, так что полное время работы алгоритма равно 6(с((п + 2')) = 6((6/т)(п + 2')). ° Выберем для двух заданных значений и и 6 такую величину т < Ь, которая бы минимизировала выражение (Ь/т)(и + 2').
Если Ь < 118п), то для любого значения т < 6 имеем (и + 2') = Э(п). Таким образом, выбор т = 6 приводит к асимптотически оптимальному времени работы (6/Ь)(и + 2") = 0(и). Если же 6 ) ~18п), то наилучшее время с точностью до постоянного множителя можно получить, выбрав т = 118 п). Зто можно понять из следующих рассуждений.
Если выбрать т = (18 п), то время работы алгоритма будет равно 0(Ьп/18 и). Если т увеличивается и превышает значение (18 п), то член 2" в числителе возрастает быстрее, чем член т в знаменателе, так что увеличение т свыше (18 п3' приводит ко времени работы алгоритма, равному П(Ьп/18п). Если же величина т уменьшается и становится меньше )18п), то член Ь/т возрастает, а множитель и+ 2' остается величиной порядка 0(п). Является ли поразрядная сортировка более предпочтительной, чем сортировка сравнением, например быстрая сортировка? Если Ь = 0(18п), как это часто бывает, и мы выбираем т — 18 и, то время работы алгоритма поразрядной сортировки равно 6(п), что выглядит предпочтительнее ожидаемого времени выполнения быстрой сортировки В(п 18п).
Однако в этих 0-выражениях совершенно реева 8. Сортировка ла линейное вренл разные постоянные множители. Несмотря на то что для поразрядной сортировки п ключей может понадобиться меньше проходов, чем для их быстрой сортировки, каждый проход при поразрядной сортировке может длиться существенно дольше. Выбор подходящего алгоритма сортировки зависит от характеристик реализации алгоритма, от машины, на которой производится сортировка (например, при быстрой сортировке аппаратный кеш часто используется эффективнее, чем при поразрядной сортировке), а также от входных данных. Кроме того, в версии поразрядной сортировки, в которой в качестве промежуточного этапа используется устойчивая сортировка подсчетом, обработка элементов производится с привлечением дополнительной памяти, которая не нужна во многих алгоритмах сортировки сравнением со временем работы 0(п1яп). Таким образом, если в первую очередь нужно учитывать объем расходуемой памяти, может оказаться более предпочтительным использование алгоритма, в котором элементы обрабатываются на месте, например алгоритма быстрой сортировки.
упражнении 8.3.1 Используя рис.8.3 в качестве образца, проиллюстрируйте работу алгоритма йяшх-Бокт со следующим списком английских слов: С0%, РОО, БЕА, йл10, К0%, МОВ, ВОХ, ТАВ, ВАК, ЕАК, ТАК, 010, В10, ТЕА, )к10%, ЕОХ. 8.3.2 Какие из перечисленных ниже алгоритмов сортировки устойчивы: сортировка вставкой, сортировка слиянием, пирамидальная сортировка, быстрая сортировка? Приведите простую схему, в результате применения которой любой алгоритм сортировки становится устойчивым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
