Алгоритмы - построение и анализ (1021735), страница 44
Текст из файла (страница 44)
После этого оператор получал возможность извлечь перфокарты из всех приемников и разместить их так, чтобы сверху находились перфокарты с пробитым первым разрядом, за ними — перфокарты с пробитым вторым разрядом и т.д. Глава 8. Сортировка эа линейное время 227 "*?6 436 - -~. 467 667 339 339 436 4.1 7 617 776 639 617 7? 6 776 329 436 --Э 639 363 437 667 Рис. 8.3. Обработка процедурой по- разрядной сортировки списка из се- ми трехзначных чисел При записи десятичных цифр в каждом столбце используются лишь первые 10 разрядов (остальные два разряда нужны для кодирования символов, отличных от цифр). Таким образом, число, состоящее из и' цифр, занимает поле из и' столбцов. Поскольку сортировщик за один раз может обработать только один столбец, для решения задачи о сортировке и перфокарт в порядке возрастания записанных на них и'-значных чисел требуется разработать некий алгоритм сортировки.
Интуиция подсказывает способ сортировки, при котором выполняется сортировка по старшей цифре, а затем полученные стопки рекурсивно сортируются по следующим в порядке старшинства цифрам. К сожалению, в этом случае возникает большое количество промежуточных стопок перфокарт (после первой же сортировки по старшей цифре — 10 стопок), за которыми нужно следить (см. упражнение 8.3-5.). В алгоритме поразрядной сортировки поставленная задача решается способом, противоположным тому, что подсказывает интуиция. Сначала производится сортировка по младшей цифре, после чего перфокарты снова объединяются в одну колоду, в которой сначала идут перфокарты из нулевого приемника, затем — из первого приемника, затем — из второго и т.д.
После этого вся колода снова сортируется по предпоследней цифре, и перфокарты вновь собираются в одну стопку тем же образом. Процесс продолжается до тех пор, пока перфокарты не окажутся отсортированными по всем и' цифрам. После этого перфокарты оказываются полностью отсортированы в порядке возрастания и'-злачных чисел. Таким образом, для сортировки перфокарт требуется лишь и' проходов колоды.
На рис. 8.3 показано, как поразрядная сортировка обрабатывает "колоду" из семи трехзначных чисел. В крайнем левом столбце показаны входные числа, а в последующих столбцах — последовательные состояния списка после его сортировки по цифрам, начиная с младшей. Серым цветом выделен текущий разряд, по которому производится сортировка, в результате чего получается следующий (расположенный справа) столбец. Важно, чтобы сортировка по цифрам того или иного разряда в этом алгоритме обладала устойчивостью.
Сортировка, которая производится сортировщиком пер- Часть 11. Сортировка и порядковая статистика 228 фокарт, устойчива, но оператор должен также следить за тем, чтобы не перепутать порядок перфокарт после извлечения их из приемника. Это важно, несмотря на то, что на всех перфокартах из одного и того же приемника в столбце, номер которого соответствует этапу обработки, стоит одна и та же цифра.
В типичных компьютерах, представляющих собой машины с произвольным доступом к памяти, поразрядная сортировка иногда применяется для приведения в порядок записей, ключи которых разбиты на несколько полей. Например, пусть нужно выполнить сортировку дат по трем ключам: год, месяц и день. Для этого можно было бы запустить алгоритм сортировки с функцией сравнения, в котором в двух заданных датах сначала бы сравнивались годы, при их совпадении сравнивались месяцы, а при совпадении и тех, и других сравнивались бы дни.
Можно поступить и по-другому, т.е. выполнить трехкратную сортировку с помощью устойчивой процедуры: сначала по дням, потом по месяцам и наконец по годам. Разработать код поразрядной сортировки не составляет труда. В приведенной ниже процедуре предполагается, что каждый из и элементов массива А — это число, в котором всего Н цифр, причем первая цифра стоит в самом младшем разряде, а цифра под номером Ы вЂ” в самом старшем разряде: Влгих Яокт(А, Н) 1 хогг -1Год 2 йо Устойчивая сортировка массива А по ~-ой цифре Лемма 8.3. Пусть имеется и Ы-значных чисел, в которых каждая цифра принимает одно из Й возможных значений. Тогда алгоритм Вл~нх Яокт позволяет выполнить корректную сортировку этих чисел за время 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ис1се2з), а затем распределить по этим карманам и входных величин. Поскольку входные числа равномерно распределены в интервале [О, 1), мы предполагаем, что в каждый из карманов попадет ке много элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
