Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 93
Текст из файла (страница 93)
Итак, метод быстрой сортировки в среднем не плох, но, конечно, в наихудшем случае он ужасен и уступает даже методу пузырька, обсуждавшемуся выше. Тем не менее рандомизация сделает наихудший случай весьма маловероятным. Поразрядная сортировка.
Обменную поразрядную сортировку (алгоритм 5.2.2К) можно аналогичным образом приспособить для сортировки с двумя лентамн, так как этот метод очень похож на быструю сортпровку. В качестве тркжа, который позволяет применить оба эти метода, можно воспользоваться идеей многократного чтения файла — тем, чего мы никогда не делали в предыдущих алгоритмах для работы с лентами. Тот же трюк позволяет осуществить обычную поразрядную сортировку на двух лентах "сначала по младшей цифре". Имея исходные данные на Т1, копируем на Т2 все записи, ключ которых в двоичной системе оканчивается нулем. Затем, после перемотки Т1, читаем ее вновь, копируя записи с ключами, оканчивающимися единицей.
Теперь перематываются обе ленты и выполняется аналогичная пара проходов, но с заменой Т1 лентой Т2 и использованием предпоследней двоичной цифры. В этот момент на Т1 будут содержаться все записи с ключами (... 00)м за которыми следуют записи с ключами (... 01)э, затем — (...
10)э, затем — (... 11)э. Если ключи имеют размер Ь бит, то, чтобы завершить сортировку, потребуется только 25 проходов по всему файлу. Подобную поразрядную сортировку можно применять только к старшим Ь бит ключа для некоторого разумно выбранного числа Ь; таким образом„если ключи были равномерно распределены, число инверсий уменьшится примерно в 2э раз, После этого несколько проходов Р-путевой сортировки методом пузырька позволят завершить работу. Новый, но несколько более сложный подход к распределяющей сортировке с двумя лентами предложили А.
И. Никитин и Л. И. Шолмов (Кибернетика 2,6 (1966), 79-84]. Имеются счетчики числа ключей (по одному на каждуто возможную конфигурацию старших битов), на основе которых строятся искусственные ключи к~, кэ,..., км так, чтобы для каждого ( число действительных ключей, лежащих между к; н к,~м находилось в заранее заданном диапазоне между Рт и Рэ. Таким образом, М лежит между (М/РЦ и (Ф/Р~). Если счетчики старших битов не дают достаточной информации для определения таких хм кю...,км, то делается еще один нли более проходов для подсчета частоты конфигураций менее значащих битов при некоторьж конфигурациях старших битов. После того как таблица искусственных ключей построена., 2(16М) проходов будетдостаточнодля завершения сортировки.
(Данный метод требует объема оперативной памяти, пропорционального Х, и поэтому не может использоваться для внешней сортировки при Х -э оо, На практике мы не станем применять его для файлов на нескольких бобинал, и, следовательно, М будет сравнительно невелико, так что таблица искусственных ключей легко поместится в памяти.) Имитация дополнительных лент. Ф. К.
Хенни (Р. С. Непше) и Р. Э. Стирнз (Н. Е. Ясеагпн) изобрели общий метод имитации /с лент всего на двух лентах, причем таким образом, что требуемое суммарное перемещение ленты возраствет всего лишь и 0((ой Е) раз, где Х вЂ” максимальное расстояние, которое нужно пройти на любой одной ленте [.74СМ 13 (1966), 533-546).
Их построение в случае сортировки можно слегка упростить, что и сделано в следующем методе, предложенном Р. М. Карпом. Будем имитировать обычное сбалансированное слияние на четырех лентах, используя две ленты: Т1 и Т2. На первой из них (т. е. на Т1) содержимое имитиру.- емых лент хранится так, как изображено на рис. 86. Представим себе, что данные записаны на четырех "дорожках" по одной для каждой имитируемой ленты. (В действительности лента не имеет таких дорожек. 54ы просто будем считывать блоки 1, 5, 9, 13,..., как дорожку 1, блоки 2, 6, 10, 14,..., как дорожку 2, и т.
д.) Другая лента (Т2) используется только для вспомогательного хранения, чтобы помочь в выполнении перестановок на Т1. Зона 3 Зона С Зона 1 Зона 2 Дорожка 1 Доромаса 2 Дорожка 3 Дорвкка 4 Рнс. 86. Разбивка ленты Т1 н конструкции Хенпи-Стирнза ('непустые зоны заштрихованы). Блоки на каждой дорожке разделяются на зоны, содержащие соответственно 1, 2, 4, 8, ..., 2", ... блоков. Зона к на каждой дорожке либо заполнена точно 2~ блоками данных, либо пуста. Например, на рис. 86 на дорожке 1 данные содержатся в зонах 1 и 3, на-дорожке 2 — в зонах О, 1 и 2, на дорожке 3 — в зонах 0 и 2, на дорожке 4 — - в зоне 1, а все остальные зоны пусты.
Предположим, что мы выполняем слияние данных с дорожек 1 и 2 на дорожку 3, В оперативной памяти находятся два буфера, используемые двухпутевым слиянием для ввода, а также третий буфер — для вывода. Когда буфер ввода для дорожки 1 станет пустым, можно заполнить его следующим образом: найти первую непустую зону дорожки 1, скажем зону к, и скопировать ее первый блок в буфер ввода, затем скопировать остальные 2ь — 1 блоков данных на Т2 и переместить их в зоны О, 1, ..., к-1 дорожки 1.
(Теперь зоны О, 1, ..., А--1 заполнены, зона й пуста.) Лналогнчная процедура используется, чтобы заполнить буфер ввода для дорожки 2, как только он станет пустым. Когда буфер вывода подготовлен для записи на дорожку 3, мы обращаем этот процесс, т. е. просматриваем Т1, пока не найдется первая пустая зона на дорожке 3, скажем зона к, и в то же время копируем данные из зон О, 1, ..., к — 1 на Т2. Данные на Т2, к которым присоединяется содержимое буфера вывода, используются теперь для заполнения зоны 1г на дорожке 3.
Ддя этой процедуры необходимо уметь выполнять запись в середину ленты Т1, не разруцшя последующую информацию. Как и в г ~учае осциллирующей сортировки с прямым чтением (раздел 5.4.5), можно без опасений выполнять это действие, если принять меры предосторожности. Поскольку просмотр до зоны /г осуществляется только один раз за каждые 2ь шагов, то, чтобы переписать 2' — 1 блоков с дорожки 1 в память, потребуется переместить ленту на 2„ .л<, 2' ' " с . 2" = с!2' ~, где с — некоторая константа. Таким образом, каждый йроход слияния требует 0(йг1ойЮ) шагов.
Поскольку в сбалансированном слиянии имеется 0(1ойХ) проходов, общее время работы будет составлять 0(Ю(1ойЮ) ). что асимптотически значительно лучше, чем наихудший случай для быстрой сортировки. На самом же деле этот метод оказывается почти бесполезным, если применяется для сортировки 100,000 записей из примера раздела 5.4.5, поскольку информация, которая должна размещаться на ленте Т1, яе поместится иа одной бобине ленты. И даже если мы пренебрежем этим фактом и будем исходить из самых оптимистических предположений относительно совмещения чтения/записи/вычислений„относительно длин междублочных промежутков и т. д., то найдем, что для выполнения сортировки потребуется около 37 ч1 Итак, этот метод представляет чисто академический интерес: константа в 0(Х(!ой Х)т) слишком велика, чтобы метод можно было эффективно использовать при реальных значениях Х.
Одноленточная сортировка. Можно ли обойтись всего одной лентой? Нетрудно видеть, что сортировку методом пузырька Р-го порядка можно преобразовать в одноленточную сортировку, но результат будет ужасен. Г. Б. Демут [РЬ. В. гЬез)з (Вгап!огг) Пп)хегз!гу, 1955), 65) сделал вывод, что в компьютере с ограниченной оперативной памятью после просмотра ограниченного участка ленты нельзя уменьшить число инверсий перестановки болыпе чем на ограниченную величину. Следовательно, любой алгоритм сортировки с одной лентой потребует в среднем не более чем ХзИ единиц времени (где Н вЂ” некоторая положительная константа, зависящая от конфигурации компьютера).
Р. М. Карп нашел очень интересный подход к исследованию этой задачи, обнаружив то, что, по существу, является оптимальным способом сортировки с одной лентой. При анализе алгоритма Карпа удобно следующим образом переформулировать задачу: как быстрее всею перевезти людей между этажами. если работает только один ли15ту (См. СотЫпагог!а) А15оНгЬтз, ейск Ьу Влада!1 Еизгш (А!йоНсЬппсз Ргезз, 1972), 17-21.) Рассмотрим здание с н этажами; помещение каждого этажа рассчитано на 6 человек.
В этом здании нет ни окон, ни дверей, ни лестниц, но есть лифт, который может останавливаться на любом этаже. В здании находятся Ьп человек., и ровно 5 из них хотят попасть на свой этаж. В лифт вмещается самое большее т человек, и он затрачивает одну единицу времени для перемещения с этажа ! на эшж (+ 1. Как найти самый быстрый способ перемещения всех людей на нужные этажи, если требуется, чтобы лифт начал и закончил свое движение на первом этаже? Нетрудно заметить связь между этой задачей и одноленточной сортировкой: люди — это записи, здание — лента, этажи — отдельные блоки на ленте, а лифт — оперативная память компьютера. Действиям программ для компьютера свойственна большая гибкость, чем действиям лифтера (программа может, напри- Рис.
87. Алгоритм Карпа лля примера с лифтом. мер, создавать двойников или, разрезав человека на две части, оставить их на время на разных этажах и т. д.), но в приведенном ниже алгоритме задача решается самым быстрым мыслимым способом без выполнения таких операций. Алгоритм Карпа (рис. 87) использует два следующих вспомогательных массива: ню 1 < й< и: число людей на этажах < й, стремящихся попасть на этажи > й; йы 1<В<я: число людей на этажах >й, стремящихся попасть на этажи <к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
