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