Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 36

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

Процедура СС(1, т): Если 1 < г, то ~1+г! Положить т = ~ — ~; 2 Вызов СС(1, т); Вызов СС(т+ 1, г); Слияние(1, т, т); Конец процедуры. 210 ГЛАВА 5. Алгоритмы и рекурсия Прежде чем перейти к объяснению процедуры СС, нам нужно описать процедуру "Слияние". Процедура "Слияние" просто берет два уже упорядоченных списка и сравнивает их первые элементы. Меньший из этих двух элементов удаляется из своего списка и помещается в некий новый список в качестве первого элемента.

Затем процедура повторяется, и всякий раз удаляемый элемент дописывается в конец нового списка. Это продолжается до тех пор, пока один из списков не опустеет. Затем остаток другого списка дописывается в конец нового списка. Полученный таким образом список и есть результат сортировки. Мы не будем формализовать процедуру "Слияние", т.к. метод ее практической реализации будет зависеть от используемой вычислительной техники.

Процедура Слияние(~, т, г): Пусть А = (аиа~ч.ыаььз,...,а ), В = (а ьыа ч.а,а +,,...,а„), и С вЂ” новый список, результат слияния; Если А и В содержат в списках элементы данных, то Сравнить первые элементы А и В и удалить меньший элемент из его множества; Добавить удаленный элемент в конец списка С; Если А или В не содержат элементов, то добавить остаток другого списка в конец списка С; Переобозначить список С как (аы апач.д,а~ч.з,...,а„); Конец процедуры.

Пусть с, Ь,а,и, И, Ы, х, е — список для сортировки, и символ ~ обозначает разбиение. На первом шаге список разбивается так: с,Ь,а,и(И,д,х,е. Затем, поскольку в начале каждой записи стоит команда "вызов СС", мы снова вызываем процедуру СС для левой части, получая разбиение с, Ь|а, и~И, д, х, е. Следующий вызов процедуры СС для левой части дает разбиение с)6(а, и)И, Н,х, е. Левую часть мы больше разбивать не можем, поэтому пытаемся разбить правую часть, чего опять-таки сделать не можем. Тогда мы производим слияние с и Ь, получая Ь,с~а,и(И,й,х,е. Далее возвращаемся к вызову процедуры СС, в котором разделяются Ь, с и а, и. Вызов СС(1, т) для левой части полностью завершен, поэтому переходим к вызову процедуры СС(т,г) для правой части, получая разбиение Ь, с~а~и(И, Н, х, е.

Не имея более возможности вызвать процедуру СС, производим слияние а и о. В результате получаем разбиение Ьс)а,и)И, Н, х,е. Затем возврашаемся на тот уровень СС, где разделяются Ь,с и а, и. Итак, мы завершили вызовы СС(1,т) и СС(т,г) и можем произвести слияние Ь,с и а,с, получая разбиение а, Ь,с,и, )И,д,х,е.

Теперь возвращаемся на тот уровень СС, где было получено разбиение на с,Ь,а,и и И,д,х,е. Завершив, таким образом, вызов СС(1,т), активизируем вызов СС(т, г), получая разбиение а, Ь, с, и, ~И, ~~х, е. Снова вызываем СС для разделения И и д; получаем разбиение а, Ь,с, и, )И)Н)х,е. Поскольку мы больше не можем использовать процедуру СС, то производим слияние И и с~, получая а, Ь,с, и, )Н,И(х,е. Затем возвращаемся на уровень СС, где разделяются И,д и х,е.

Дальнейшее использование процедуры СС(1,т) невозможно, поэтому мы переходим к вызову СС(т,г), получая разбиение а, Ь,с,о, (Ы,И)х(е. Теперь переходим к процедуре "Слияние" для осуществления слияния х и е, после чего получаем а, Ь,с, и, ф, И~е, х. Опять возвращаемся на тот уровень СС, где разделя- РАЗДЕЛ 5.4.

Алгоритмы сортировки 211 ются й,п' и х,е. Обе команды СС выполнены, поэтому производим слияние г(,й и е,л, получая а,б,с,и)11,е,й,х. В конечном счете мы возвращаемся на уровень СС, где разбиение проходит между с, Ь, а, и и й, Ы, х, е. На этом уровне выполнены обе команды СС, поэтому мы производим слияние а, Ь, с, и и г(, е, й, х, получая а, Ь, с, г(, е, й, и, г. На этом процедура завершена. По количеству операций сравнения процедура СС относится к числу наиболее эффективных.

Для доказательства этого факта предположим, что п = 2 для некоторого значения т. Отсюда т = 1окзп. Для фиксированного т зто самый неблагоприятный случай, Если рассмотреть слияние, выполняемое начальным вызовом процедуры сортировки, то проводится слияние 2 (= 21) списков, каждый из которых содержит 2 ' элементов.

Эта ситуация соответствует первому уровню. Вообще, на й-ом уровне имеется 2" списков, в каждом по 2 " элементов. Необходимо провести 2ь ' сравнений пар списков, по 2 " элементов в каждом. Каждое сравнение пар списков требует не более 2 "+' — 1 сравнений, поскольку один оставшийся элемент не должен сравниваться с каким-либо. Следовательно, на й-ом уровне будет не более 2~ ' (2 ~ч 1 — 1) = 2" ' (2 1ь+-'1 — 1) операций сравнения. Поэтому общее число операций сравнения не превышает т — 1 ~2~ (2 1"~-~1 — 1) = ~~1 21.

(2 ' — 1) = Ь=1 *=о т — 1 = ~~> 2 — 2' = гп2™ — (2 — 1) = п(ока п — (и — 1), и поэтому в самом неудачном случае число сравнений имеет порядок О(п!пп). Последней рассмотрим сортировку, которая называется сортировка вставками. Процедура для этой сортировки действительно очень простая. При этом методе сортировки элементы данных выбираются по одному и помещаются во вновь создаваемом списке на соответствующее место. При этом, если место элементу найдено, то все другие вставляемые элементы располагают левее, если они меньше, и правее, если они больше.

Опять рассмотрим тот же список для сортировки с,б,а,и,й,И,х,е. Первым выбираем с и помещаем его в новом списке. Далее, поскольку Ь меньше с, помещаем его перед с, формируя Ь,с. Следующим выбираем а. Поскольку оно меньше Ь, помещаем его перед Ь, формируя а,6, с. Далее выбираем и. Оно больше с, поэтому помещаем его после с, формируя а, Ь, с, и. Поскольку й меньше, чем и, и больше, чем с, помещаем его между с и и, формируя список а, Ь,с, й,и. Теперь рассматриваем г(. Оно больше, чем с, и меньше, чем й, поэтому помещаем его между с и й, что дает а, 6, с, 11, й, и. Поскольку х больше и, помещаем его после и, получая а, Ь, с, 1(, й, и, л.

Наконец, поскольку е больше, чем 11, и меньше, чем й, помещаем его между и' и й, формируя рассортированный список а,Ь,с,д,е,й,и,т. В самом плохом варианте число операций сравнения на каждом этапе такое же, как в пузырьковой сортировке, т.е. имеет порядок О(пз). 212 ГЛАВА 5. Алгоритмы и рекурсия И быстрая сортировка, и сортировка слиянием рекурсивно определяют разбиение множества на меньшие множества, сортировку этих меньших множеств и последующую сборку этих рассортированных множеств.

Такой метод разбиения множества на подмножества, выполнения операций над ними и обратной сборки множеств вместе называется методом "разделяй и властвуй". Как правило, это весьма эффективный подход к решению задач. Очень часто процедуры типа "разделяй и властвуй", такие как приведенная выше, удовлетворяют рекурсивному соотношению вида Я„= СЯ- + 7"(п), где Я„может характеризовать число операций, число сравнений, затрачиваемое время или другие параметры. В данном разделе в качестве такой характеристики будем рассматривать число операций.

Функция 7" 1п) описывает число операций, затрачиваемых на разделение множества на два множества и последующую сборку этих двух подмножеств в целое. Когда используется запись г как индекс в формуле, это предполагает, что множество данных, над которым производится действие, разбивается на две равные части.

Это достаточно распространенная ситуация, т.к, наиболее часто используются бинарные деревья или другие понятия, содержащие бинарные операции. Если бы множество делилось на й равных частей, была бы использована запись -"„. Предполагается также, что и является некоторой степенью числа 2. Нас, в основном, будут интересовать случаи, когда Дп) равно константе и когда )'(п) = Рп для некоторого постоянного Р. Использование записи 7"(п) = Рп равносильно предположению, что число операций для разбиения и последующего соединения п объектов прямо пропорционально количеству элементов множества. При изучении эффективности быстрой сортировки было показано, что решение рекурсивного соотношения Я„= 2Я- + п, где и— степень числа 2, имеет вид п1СУг + 1ойз(п)). Это частный слУчай РешениЯ длЯ соотношения Я„= СЯ- + Рп, когда С = 2 и Р = 1.

Для С > 2 решением рекурсивного соотношения будет я„= Ап"г с + ( зю ) п, где А выбрано таким обРазом, что Я1 = А + згос,. Если 7"1п) = Р, где Р— некоторая константа, то решением рекурсивного рс ~ггс соотношения Су„= СЯ- + Р для С ф 1 будет Я„= ", В частном случае, когда С = 2, решение упрощается до Я„= Р(2п — 1).

Изучение такого рода рекурсивных соотношений будет продолжено при решении конкретных задач. К сожалению, целое число п в общем случае не является степенью числа 2. Однако, если предположить, что ߄— возрастающая функция и и меньше некоторого а, где а — степень числа 2, то Я„< Я, т.е. функция Я„ограничена сверху. ° УПРАЖНЕНИЯ 1. Рассортируйте последовательность 7, 11, 4, О, 3, 1, 9, 4, 2, 8, используя: а) сортировку выбором; б) пузырьковую сортировку; в) быструю сортировку; г) сортировку слиянием; д) сортировку вставками.

РЯЗДЕЛ 5.4. Яоворитмы сортировки 213 2. Рассортируйте последовательность 12, 50, -1, -10, 10, 11, 52, 30, 2, 8, -12, используя: а) сортировку выбором; б) пузырьковую сортировку; в) быструю сортировку; г) сортировку слиянием; д) сортировку вставками. 3. Рассортируйте последовательность х,а, с, у,р, х, Г, 1, т, у,и, 6, д,п, в, г, используя: а) сортировку выбором; б) пузырьковую сортировку; в) быструю сортировку; г) сортировку слиянием; д) сортировку вставками. 4. Рассортируйте последовательность Джонсон, Браун, Блэк, Джексон, Мэрфи, Смит, Джонс, используя: а) сортировку выбором; б) пузырьковую сортировку; в) быструю сортировку; г) сортировку слиянием; д) сортировку вставками.

Характеристики

Список файлов книги