Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 50
Текст из файла (страница 50)
Предположим, что алгоритм сортировки сравнением с обменом без запоминания Х неверно сортирует массив А[1 .. и]. Пусть А[р] — наименьшее значение в А, которое алгоритм Х помещает в неверную позицию, и пусть А[Ч] представляет собой значение, которое алгоритм Х перемещает в позицию, в которую должно было попасть значение А[р]. Опреде- л39 Глава д Сортировка ла линейное еркин лим массив В[1 ..
и] из О и 1 следуюшим образом. / О, если А[1) < А[р), 1, 1, если А[в) > А[р) . а Докажите, что А[д) > А[р), так что В [р) = О и В[а) = 1. б. Дла завершения доказательства О-1-леммы сортировки докажите, что алгоритм Х неверно сортирует массив В. Теперь используем О-1-лемму сортировки для доказательства того, что конкретный алгоритм сортировки работает корректно. Алгоритм сорлзнроякн сввалдцами (со!шппзог1) работает с прямоугольным массивом из и элементов.
Массив имеет г строк и о столбцов (так что п = га), удовлетворяющих следующим ограничениям: г должно быть четным; а должно быть делителем г; г > 2аз. По завершении сортировки столбцами массив оказывается отсортированным в порядке етарнвннелвва елваабдов: при чтении столбцов сверху вниз и слева направо элементы монотонно увеличиваются. Сортировка столбцами работает за восемь шагов независимо от значения и. Все нечетные шаги одинаковы: отдельная сортировка каждого столбца.
Каждый четный шаг представляет собой фиксированную перестановку. Вот эти шаги. 1. Отсортировать каждый столбец. 2. Транспонировать массив, но вновь привести его к виду с г строками и а столбцами. Другими словами, преобразовать крайний слева столбец поочередно в г~а верхних строк; затем преобразовать следующий столбец в следующие г/о строк и т.д. 3. Отсортировать каждый столбец. 4. Выполнить инверсию перестановки, выполняемой на шаге 2. 5.
Отсортировать каждый столбец. б. Сдвинуть верхнюю половину каждого столбца в нижнюю, а нижнюю — в верхнюю половину столбца справа. Оставить верхнюю половину крайнего слева столбца пустой, а нижнюю часть крайнего справа столбца сдвинуть в верхнюю половину нового крайнего справа столбца, оставляя пустой нижнюю половину этого нового столбца. 7. Отсортировать каждый столбец.
8. Выполнить обращение перестановки, выполняемой на шаге 6. Часть Рй Сортировка и порядковая статистика 240 16 17 18 5 10 6 13 7 15 1 4 11 2 8 12 3 9 14 (ж) Рне. 8.5. Шаги сортировки столбцами. (а) Входной массив с шестью строками н гремя столбцамн.
(б) После сортировки столбцов на шаге ). (в) После транепоннрованвя н изменения формы на шаге 2, (г) После сортировки столбцов на шаге 3. (д) После выполнения шага 4, обращающего перестановку на шаге 2. (е) После сортировки столбцов на шаге 5, (ж) После сдвига на полстолбца на шаге б. (з) После соргнровкн столбцов на шаге' ). (н) После выполнения шага 8, обращающего перестановку на шаге б, теперь массив огеоргнрован в порядке старшинства столбцов. На рис. 8.5 показан пример выполнения шагов сортировки столбцами при г = 6 и в = 3. (Этот пример работает, несмотря даже на то, что в нем нарушено требо- вание т ) 2вз.) в.
Докажите, что можно рассматривать сортировку столбцами как алгоритм сортировки сравнением с обменом без запоминания, даже если мы не знаем, какой метод сортировки используется на нечетных шагах. Хотя в корректность алгоритма сортировки сравнением с обменом без запоминания может быть трудно поверить, для доказательства этого факта можно воспользоваться 0-1-леммой сортировки. Эта лемма применима, поскольку сортировку столбцами можно рассматривать как алгоритм сортировки сравнением с обменом без запоминания.
Пара определений поможет вам применить 0-1-лемму сортировки. Мы говорим, что область массива чистая (с)сап), если она содержит только нули или только единицы. В противном случае область может содержать как нули, так и единицы, и является грязной (6(пу). Впредь будем считать, что входной массив содержит толью нули и единицы и что его можно рассматривать как массив с т строками и в столбцами. а Докажите, что после шагов 1-3 массив состоит из некоторых чистых строк из нулей вверху, нескольких чистых строк с единицами внизу и не более чем нз в грязных строк между ними.
10 14 5 8 7 17 12 1 6 16 9 11 4 15 2 18 3 13 (а) 1 4 11 2 8 12 3 9 14 5 10 16 6 13 17 7 15 18 (е) 4 8 10 12 16 18 1 2 3 5 7 6 9 11 14 13 15 17 (б) 4 8 10 12 16 18 3 9 14 15 2 5 6 11 13 17 (в) 4 10 16 5И17 6 12 18 1 7 13 2 8 14 3 9 15 (3) 1 3 6 2 5 7 4 8 10 9 13 15 11 14 17 12 16 18 (г) 1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12 18 (и) 1 4 11 3 8 14 6 10 17 2 9 12 5 13 16 7 15 18 (д) л41 Глава д Сортировка за линейное врали д.
Докажите, что после шага 4 массив при чтении в порядке старшинства столбцов начинается с чистой области, состоящей из нулей, а заканчивается чистой областью, состоящей из единиц, и имеет посредине грязную область не более чем из 00 элементов. е. Докажите, что шаги 5-8 генерируют полностью отсортированный 0-1-выход. Сделайте отсюда вывод о том, что сортировка столбцами корректно сортирует все входные данные с произвольными значениями. ж Теперь предположим, что 0 не является делителем г.
Докажите, что после шагов 1-3 массив состоит из нескольких чистых строк из нулей вверху, нескольких чистых строк из единиц внизу и не более чем из 20 — 1 грязных строк между ними. Насколько большим по сравнению с т должно быть значение 0, побы сортировка столбцами работала корректно, когда 0 не является делителем г? з. Предложите простое изменение шага 1, которое позволяет обеспечить требование г > 200 даже при 0, не являющемся делителем г, и докажите, что это изменение не влияет на корректность работы алгоритма. Заключительные замечания Использовать модель дерева решений при изучении алгоритмов сортировки сравнением впервые предложили Форд (РоЫ) и Джонсон ()оЬпзоп) [109).
В томе Оскуссвгеа программирования Кнута (Кппйг), посвященном сортировке [2101', описываются различные разновидности задачи сортировки, включая приведенную здесь теоретико-информационную нижнюю границу для сложности сортировки. Полное исследование нижних границ сортировки с помощью обобщений модели дерева решений было проведено Вен-Ором (Вел-Ог) [381. Согласно Кнуту сортировка подсчетом впервые была предложена Х.Г. Сьювардом (Н.Н.
Яегнагг)) в 1954 году; ему также принадлежит идея объединения сортировки подсчетом и поразрядной сортировки. Оказывается, что поразрядная сортировка, начинающаяся с самой младшей значащей цифры, — по сути "народный" алгоритм, широко применявшийся операторами механических машин, предназначенных для сортировки перфокарт. Как утверждает Кнут, первая ссылка на этот метод появилась в документе, составленном Л.Д. Комри (Ь.Л Сошпе) и опубликованном в 1929 году, где описывается счетно-перфорационное оборудование.
Карманная сортировка используется с 1956 года, с того времени, когда И.Д. Исаак (Е.3. 1ааас) и Р.К. Синглтон (К.С. бйп81егоп) предложили основную идею этого метода [1871. гимсегся русский перевод: д. Киуг. Ослусство Чзограииированмг, т. я Сортировка н конек, 2-е нза— М . И Д. "Вильямс", 2000. Часть Рд Сортировка а яорядкоеая статьсян. Мунро (Мнпго) и Раман (Кашап) [261] предложили устойчивый алгоритм сортировки, который в наихудшем случае выполняет О(п"+') сравнений, где 0 < с < 1 — произвольная константа.
Несмотря на то что в алгоритмах, время выполнения которых равно О(п 18 п), выполняется меньше сравнений, в азгорнтме Мунро и Рамана данные перемешаются 0(п) раз, и он выполняет сортировкк на месте. Случай сортировки п 6-битовых чисел за время о(п 18 и) рассматривался многими исследователями.
Было получено несколько положительных результатов, в каждом из которых незначительно менялись предположения о вычислительной модели, а также накладываемые на алгоритм ограничения. Во всех случаях предполагалось, что память компьютера разделена на адресуемые 6-битовые слова. Фредман (Ргейпап) и Виллард (%111агд) [114] первыми предложили использовать дерево слияний (йз(оп ггее) и выполнять с его помощью сортировку п целых чисел за время 0(п 18 и( 18 18 и). Впоследствии эта граница была улучшена Андерссоном (Апдегавоп) [16] до О(пьс[8и).
В этих алгоритмах применяются операция умножения, а также некоторые предварительно вычисляемые константы. Андерссон, Хейгерап (Найепзр), Нильсон (%1ззоп) и Раман [17] показали, как выполнить сортировку и чисел за время О(п18 18 и), ие прибегая при этом к умножению, однако этот метод требует дополнительной памяти, объем которой может неограниченно увеличиваться с ростом п. С помощью мультипликативного хеширования объем этой памяти можно уменьшить до величины 0(п), но при этом граница для наихудшего случая 0(п!8 18 и) становится границей для математического ожидания времени работы.
Обобщив экспоненциальные деревья поиска Андерссона [16], Торуп (Т]зогир) [333] сформулировал алгоритм сортировки, выполняющийся в течение времени О(п(18 18п) ). В этом алгоритме не используется ни умножение, ни рандомизация, а обьем необходимой дополнительной памяти линейно зависит от количества элементов. Дополнив эти методы новыми идеями, Хан (Нап) [157] улучшил границу времени работы до 0(п 18 18п18 18 18п). Несмотря на то что упомянутые алгоритмы стали важным теоретическим достижением, все они чрезвычайно сложные, и в данный момент представляется маловероятным, чтобы они могли практически составить конкуренцию существующим алгоритмам сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
