Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 46
Текст из файла (страница 46)
Пусть имеется и Ы-значных чисел, в которых каждая цифра принимает одно из Й возможных значений. Тогда алгоритм Вл~нх Яокт позволяет выполнить корректную сортировку этих чисел за время 6 (Н1п + Й)), если устойчивая сортировка, используемая данным алгоритмом, имеет время работы 0 (п+ й). Доказательство.
Корректность поразрядной сортировки доказывается методом математической индукции по столбцам, по которым производится сортировка (см. упражнение 8.3-3). Анализ времени работы рассматриваемого алгоритма зависит от того, какой из методов устойчивой сортировки используется в качестве промежуточного алгоритма сортировки.
Если каждая цифра принадлежит интервалу от 0 до й — 1 (и, таким образом, может принимать й возможных значений), и 1с не слишком большое, то поразрядная сортировка — оптимальный выбор. Для обработки каждой из Н цифр п чисел понадобится время 9 (и+ й), а все цифры будут обработаны алгоритмом поразрядной сортировки в течение времени 9 (д (и + й)). Если И вЂ” константа, а 1с = 0 (и), то время работы алгоритма поразрядной сортировки линейно зависит от количества входных элементов. В общем случае мы получаем определенную степень свободы в выборе разбиения ключей на цифры. Глава 8. Сортировка за линейное время 229 Лемма 8.4. Пусть имеется п Ь-битовых чисел и натуральное число т < Ь.
Алгоритм ВАп~х Бокт позволяет выполнить корректную сортировку этих чисел за время Я ((Ь/т) (и+ 2")). Доказательство. Для т < Ь каждый ключ можно рассматривать как число, состоящее из Н = '1 Ь/т) цифр по т битов каждая. Все цифры представляют собой целые числа в интервале от 0 до 2" — 1, поэтому можно воспользоваться алгоритмом сортировки подсчетом, в котором й = 2" — 1 (например, 32-битовое слово можно рассматривать как число, состоящее из четырех 8-битовых цифр, так что 6 = 32, т = 8, й = 2" — 1 = 255, а И = Ь/т = 4). Каждый проход сортировки подсчетом занимает время 9(п + 6) = О (и + 2"), а всего выполняется 0 проходов, так что полное время выполнения алгоритма равно 6 (о (п + 2')) = О ((Ь/т) (и+ 2")).
и Выберем для двух заданных значений и и 6 такую величину т < Ь, которая бы сводила к минимуму выражение (6/т) (и + 2'). Если Ь < 118 п), то для любого значения т < Ь имеем (и+ 2') = 6(п). Таким образом, выбор т = Ь приводит к асимптотически оптимальному времени работы (Ь/6) (и + 2ь) = О (и). Если же 6 > '118 п), то наилучшее время с точностью до постоянного множителя можно получить, выбрав т = 118 п). Это можно понять из следующих рассуждений.
Если выбрать т = 118 п), то время выполнения алгоритма будет равно О (Ьи/18п). Если т увеличивается и превышает значение (18п)', то член 2" в числителе возрастает быстрее, чем член т в знаменателе, поэтому увеличение т приводит ко времени работы алгоритма, равному й (Ьи/18 и). Если же величина т уменьшается и становится меньше 118 п), то член Ь/т возрастает, а множитель и + 2' остается величиной порядка О (и).
Является ли поразрядная сортировка более предпочтительной, чем сортировка сравнением, например, быстрая сортировка? Если Ь = О (18 п), как это часто бывает, и мы выбираем т = 18 п, то время работы алгоритма поразрядной сортировки равно О (и), что выглядит предпочтительнее среднего времени выполнения быстрой сортировки О (и 18 и). Однако в этих выражениях, записанных в О-обозначениях, разные постоянные множители. Несмотря на то, что для поразрядной сортировки и ключей может понадобиться меньше проходов, чем для их быстрой сортировки, каждый проход при поразрядной сортировке может длиться существенно дольше.
Выбор подходящего алгоритма сортировки зависит от характеристик реализации алгоритма, от машины, на которой производится сортировка (например, при быстрой сортировке аппаратный кэш часто используется эффективнее, чем при поразрядной сортировке), а также от входных данных. Кроме того, в той версии поразрядной сортировки, в которой в качестве промежуточного этапа используется устойчивая сортировка подсчетом, обработка элементов производится с привлечением дополнительной памяти, которая не нужна во многих алгоритмах сортировки сравнением, время работы которых равно О (п18п).
Часть 18 Сортировка и порядковая статистика 230 Таким образом, если в первую очередь нужно учитывать объем расходуемой памяти, может оказаться более предпочтительным использование, например, алгоритма быстрой сортировки, в котором элементы обрабатываются на месте. Упражнения 8.3-1. Используя в качестве модели рис. 8.3, проиллюстрируйте, как с помощью процедуры Клих Зонт сортируется следующий список английских слов: С0%, РОО, БЕА, КБО, К0%, МОВ, ВОХ, ТАВ, ВАК, ЕАК, ТАК, Р10, В10, ТЕА, Х0%, ЕОХ. 8.3-2. Какие нз перечисленных ниже алгоритмов сортировки устойчивы: сортировка вставкой, сортировка слиянием, пирамидальная сортировка, быстрая сортировка? Приведите пример схемы, в результате применения которой любой алгоритм сортировки становится устойчивым. Оцените количество дополнительного времени и объем памяти, необходимые для реализации этой схемы.
8.3-3. Докажите методом математической индукции корректность работы поразрядной сортировки. Где в доказательстве используется предположение об устойчивости промежуточной сортировки? 8.3-4. Покажите, как выполнить сортировку п чисел, принадлежащих интервалу от 0 до пз — 1, за время 0(п). * 8.3-5. Определите точное количество проходов, которые понадобятся для сортировки И-злачных десятичных чисел в наихудшем случае, если используется сортировка перфокарт, начинающаяся со старшей цифры. За каким количеством стопок перфокарт нужно будет следить оператору в наихудшем случае? 8.4 Карманная сортировка Если входные элементы подчиняются равномерному закону распределения, то ожидаемое время работы алгоритма карманной сорюиироаки (Ьис1се~ зон) линейно зависит от количества входных элементов. Карманная сортировка, как и сортировка подсчетом, работает быстрее, чем алгоритмы сортировки сравнением.
Это происходит благодаря определенным предположениям о входных данных. Если при сортировке методом подсчета предполагается, что входные данные состоят из целых чисел, принадлежащих небольшому интервалу, то при карманной сортировке предполагается, что входные числа генерируются случайным процессом и равномерно распределены в интервале 10, 1) (определение равномерного распределения можно найти в разделе В.2). Глава 8.
Сортировка за линейное время 231 Рис. 8.4. Процедура Впсквт 8окт в действии Идея, лежащая в основе карманной сортировки, заключается в том, чтобы разбить интервал [О, 1) на и одинаювых интервалов, или карманов (17ис(се2з), а затем распределить по этим карманам и входных величин.
Поскольку входные числа равномерно распределены в интервале [О, 1), мы предполагаем, что в каждый из карманов попадет ке много элементов. Чтобы получить выходную последовательность, нужно просто выполнить сортировку чисел в каждом кармане, а затем последовательно перечислить элементы каждого кармана. При составлении кода карманной сортировки предполагается, что на вход подается массив А, состоящий из и элементов, и что величина каждого принадлежащего массиву элемента А [г] удовлетворяет неравенству 0 < А [1] < 1. Для работы нам понадобится вспомогательный массив связанных списюв (карманов) В [О..и — Ц; предполагается, что в нашем распоряжении имеется механизм поддержки таких списков.
(Реализация основных операций при работе со связанным списком описана в разделе 10.2.) В22СКЕТ ЯОКТ(А) 1 и — 1еидй [А] 2 аког г' - 1 1о и 3 йо Вставить элемент А[(] в список В[[иА[тЦ] 4 аког 1 — 0 1о и — 1 5 с(о Сортировка вставкой списка В[1] 6 Объединение списков В[0], В[1],..., В(и — 1] Чтобы понять, как работает этот алгоритм, рассмотрим два элемента А [(] и А [2]. Без потери общности можно предположить, что А [г] < А [2].
Поскольку [иА [(Ц < [иА [Я~, то элемент А [г] помещается либо в тот же карман, что и элемент А [2], либо в карман с меньшим индексом. В первом случае элементы 7 4 '[27[ „'7 ;: ~.72( ь [с~[ 7 [2![ 7 '2 2! , 7 — 7„-[ «с«[.63« в «7 .ч --'"', *«27«Г — ' — ~",«и««' ° -3" 2 «[ — « — «[ '2772 —; — э 7 26[, « ' « —,'-~ЪЛ,~ ~ : " -2- .Г«ьз( [,!-.2Т-+ «-Я~~7 Я [ '[ г- 7'1 ''] Часть П. Сортировка и порядковая статистика 232 Вычисляя математическое ожидание обеих частей этого уравнения и воспользо- вавшись его линейностью, с учетом уравнения (В.21) получаем: и-1 Е[Т(п)] = Е 9(п)+ ) 0(п~) '=о и-1 = 6 (п) + ~~~ Е [О (п~)] = ыо к-1 = О (п) + ~~> 0 (Е [п~]) (8.1) Мы утверждаем, что для всех г = 0,1,...,п — 1 Е [п8] = 2 — 1/п.
(8.2) Не удивительно, что каждому 1-му карману соответствует одна и та же величина Е [п~1, поскольку все элементы входного массива могут попасть в любой карман А [г] и А [т] располагаются в нужном порядке благодаря циклу 1ог в строках 4-5. Если же эти элементы попадут в разные карманы, то они разместятся в правильном порядке после выполнения строки 6.
Таким образом, карманная сортировка работает корректно. На рис. 8.4 показано, как с помощью карманной сортировки обрабатывается входной массив, состоящий из 10 чисел. В части а этого рисунка показан входной массив А [1..10]. В части б изображен массив В [0..9], состоящий из отсортированных списков после выполнения строки 5 алгоритма.
В 1-м кармане содержатся величины, принадлежащие полуоткрытому интервалу [г/10, (г + 1)/10). Отсортированная выходная последовательность представляет собой объединение списков В [О], В [1],..., В [9]. Чтобы оценить время работы алгоритма, заметим, что в наихудшем случае для выполнения всех его строк, кроме строки 5, требуется время 0 (п). Остается просуммировать полное время, которое потребуется для и вызовов алгоритма сортировки методом вставок (строка 5). Чтобы оценить стоимость этих вызовов, введем случайную величину пэ обозначающую количество элементов, попавших в карман В [1].
Поскольку время работы алгоритма сортировки вставкой является квадратичной функцией от количества входных элементов (см. раздел 2.2), время работы алгоритма карманной сортировки равно 233 с равной вероятностью. Чтобы доказать уравнение (8.2), определим для каждого г = О, 1,...,п — 1 и т' = 1, 2,...,п индикаторную случайную величину Х, = 1(А ]т] попадает в (-ый карман). Следовательно, Чтобы вычислить величину Е (п,'], раскроем квадрат и перегруппируем сла- гаемые: Е(п~] =Е х; х; =Е (8.3) 1(я<и я~у ~ ' е [х;,х„] 1(Ь (и /с~у В приведенной выше цепочке уравнений последнее равенство следует из линей- ности математического ожидания.
Отдельно оценим обе суммы. Индикаторная случайная величина Х, равна 1 с вероятностью Цп и О в противном случае, поэтому получаем: Е(Х1] =1.— +О ~1 — -) = —. и ~, п) п Когда й ~ т', величины Х; и Хсь независимы, поэтому можно записать: 1 1 1 Е]ХОХсь] = Е]ХО] Е]хсь] = п п пз Подставив эти величины в уравнение (8.3), получим: 2 1 1 1 Е ~из] = с> — + ~1 ~~1 — = п — +п(п — 1) ° — = 1 п п2 3=1 1Я<и 1<1с<и /сну и — 1 1 + — =2 — —, и и' что и доказывает уравнение (8.2).
Используя это выражение в уравнении (8.1), приходим к выводу, что математическое ожидание времени работы алгоритма карманной сортировки равно Глава 8. Сортировка за линейное время и1=~> Х;. 1=1 (Ехс) ] =и [ ЕХ2+ Х с=1 1ЯЯи = )'Е~Х2-1+ ,') 2=1 1Я<и и и ~~~, Хбхсь 2=1 Ь=1 Часть 11. Сортировка и порядковая статистика 234 6(п)+п О (2 — 1/и) = 9 (и). Таким образом, математическое ожидание времени работы алгоритма карманной сортировки в целом линейно зависит от количества входных элементов. Такая зависимость может наблюдаться даже в том случае, когда входные элементы не подчиняются закону равномерного распределения. Если входные элементы обладают тем свойством, что сумма возведенных в квадрат размеров карманов линейно зависит от количества входных элементов, уравнение (8.1) утверждает, что карманная сортировка этих данных выполняется в течение времени, линейно зависящего от количества данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
