Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 35
Текст из файла (страница 35)
5.4. АЛГОРИТМЫ СОРТИРОВКИ В этом разделе мы рассмотрим некоторые методы сортировки данных. В дальнейшем мы будем считать выполненными два условия. Во-первых, будем считать, что данные пронумерованы так, что имеется первый элемент данных, второй элемент, и так далее до п-го. Такая организация данных может быть реализована при помоши массива, указателей или еше каким-либо образом.
Конкретный метод реализации списка нас не интересует. Второе предположение состоит в том, что на множестве данных введено полное упорядочение, и мы хотим расположить 206 ГЛАВА 5. Алгоратмы и рекурсия данные в соответствии с этим порядком. Это может быть лексикографическое упорядочение (т.е. упорядочение по алфавиту) или же упорядочение в соответствии с числовыми значениями, которые приписываются элементам данных. Опять же, нас не интересует, что зто за упорядочение, лишь бы оно было задано. В дальнейшем запись а < 6 будет означать, что в нашем упорядочении а предшествует Ь.
Для начала рассмотрим сортировку выбором (СВ). Пусть аы аз, ..., а„— элементы, подлежащие сортировке. Сам процесс сортировки очень прост. Мы фиксируем элемент аг, находим наименьший элемент и меняем местами этот элемент и аы Затем переходим к аз. Рассматриваем все элементы, начиная с аз, находим среди них наименьший и меняем местами этот элемент и аз.
Процесс продолжаем до завершения. Более строго: пусть мы находимся на этапе, когда необходимо заменить а;. Введем переменную тт, для того чтобы отслеживать индекс наименьшего элемента среди а; и всех тех элементов, которые за ним следуют. Сначала полагаем туп = 4 и начинаем сравнивать оставшиеся элементы с а ,„.
Если находим элемент, который меньше а ,„, скажем аь полагаем гиги = 6 и продолжаем поиск наименьшего элемента, сравнивая его с а ,„. Если таковой находится, процесс повторяем. Дойдя до и-го элемента, меняем местами а; и а и переходим к а,еы Теперь мы можем записать алгоритм. Процедура СВ: Цикл погот1доп — 1: Положить т(и Цикл по 1' от 1 до и: Если ау < а еи то пусть тгп = ~; Конец цикла; Поменять местами а, и а„„„; Конец цикла; Конец процедуры. ПРИМЕР 5.27.
Пусть с, Ь,а,е,6,Ы вЂ” список для сортировки. Начинаем с с на позиции 1 и полагаем тгп = 1. Сравниваем с с Ь и, поскольку Ь < с и Ь находится на второй позиции, полагаем туп = 2. Далее сравниваем 6 с а и, поскольку а < Ь, полагаем гизи = 3. Букв, меньших а, не находим, поэтому меняем местами а и Ь, получая в результате а, Ь, с, и, 6, а. Повторяем процесс, начиная с Ь, поэтому тги = 2. Сравнение 6 с оставшимися буквами показывает, что ни одна из них не меньше Ь, так что тт остается равным 2, и мы меняем местами 6 с самим собой. Далее переходим к с и полагаем гиги = 3.
Опять ни один элемент не меньше с, поэтому с остается на том же месте. Переходим к е и полагаем тгп = 4. Поскольку 6 < е, то 1и1п = 5. Затем сравниваем 6 и а'. Поскольку с( < е, полагаем тгп = 6. Меняем местами И и е, получая последовательность а, Ь,с,а',6, е. Продолжаем процесс для 6, а так как 6 < и, то сортировка закончена.
П Рассмотрим число сравнений, которое производится согласно этому методу, для списка из п элементов. Первый элемент сравнивается с остальными п — 1 элементами. Второй элемент сравнивается с и — 2 элементами и так далее до (и — 1)-го элемента, который сравнивается только с одним элементом. Таким РАЗДЕЛ 5.4. Алгоритмы сортировки 207 образом, имеем (и — 1) + (и — 2) + + 2+ 1 = и(и — 1) так что число сравнений имеет порядок О(из). Теперь рассмотрим весьма популярный алгоритм сортировки, очень напоминающий сортировку выбором. Он называется иузечрьковой сортировкой (ПС), так как в нем меньшие числа поднимаются вверх, как пузырьки в воде. (В данном случае "вверх" означает налево.) Процесс начинают с правого конца списка и сравнивают два последних элемента, сдвигая меньший влево.
Затем сравнивают этот меньший с элементом, стоящим слева от него, и опять передвигают меньший из них влево. Процесс продолжают, пока не будет достигнут первый элемент. В результате наименьший элемент становится первым элементом. Затем процесс повторяется до тех пор, пока он не вернется ко второму по величине элементу.
Теперь второй по величине элемент располагается на втором месте. Процесс повторяется до тех пор, пока все элементы не будут рассортированы. На данном этапе новым является то, что при такой сортировке движение происходит с двух сторон. Процесс начинается справа, движется влево вплоть до первого элемента. Затем опять начинается справа, движется влево вплоть до второго элемента. Всякий раз движение влево осуществляется вплоть до 1- го элемента данных, при этом значение 1 возрастает.
Для описания такого рода перемещений нам понадобится новая разновидность цикла перечислением. Говоря "цикл по г от и до Ь с шагом — 1", где и > й, мы будем иметь в виду, что, начиная с г = и, мы будем шаг за шагом уменьшать значение г на 1, вплоть до г = й. Процедура ПС: Цикл по 1 от 2 до и: Цикл по ) от и доз с шагом — 1: Если а, < а и то поменять местами а, и а Конец цикла; Конец цикла; Конец процедуры. ПРИМЕР 5.28. Пусть, как и ранее, с, Ь, а, с, Ь, й — список для сортировки.
Сначала меняем местами 6 и й, поскольку й меньше, чем Ь. Затем меняем местами й и и, т.к. й меньше, чем и. На данный момент список выглядит таким образом: с, Ь, а, й, и,й. Поскольку а не меньше, чем а, мы не меняем местами а и й. Теперь меняем местами Ь и а, поскольку а меньше, чем 6. Наконец, меняем местами а и с, т.к. а меньше, чем с. Состояние списка на данном этапе — а,с, Ь, й, п,6. Повторяя процесс, меняем местами 6 и ш поскольку 6 меньше о.
Оставляем й на своем месте, т.к. 6 не меньше й. Теперь список имеет вид а, с, Ь, й, Ь, с. Также на своих местах остаются й и Ь, поскольку й не меньше Ь. Элемент Ь меньше с, поэтому Ь и с меняются местами, и мы получаем а, Ь, с, а, Ь, ш Несмотря на то, что процесс повторялся трижды, лишние перестановки не потребовались, сортировка закончилась. П Если проанализировать процесс сравнения в этом просмотре и элементов, то в первом цикле он включает и — 1 операцию, во втором — и — 2 операции.
208 ГЛАВА 5. Алгоритмы и рекурсия Процесс завершается выполнением одного сравнения в последнем цикле. Отсюда получаем п(п — 1) (и — 1) + (и — 2) + + 2 + 1 = 2 так что общее число сравнений имеет порядок 0(пз). Таким образом, полученное значение совпадает с соответствующей величиной для сортировки выбором. Несмотря на то, что число операций сравнения этих двух методов имеет один и тот же порядок, их скорости в реальных случаях могут различаться. Теперь рассмотрим алгоритм сортировки, который называется быстрой сортировкой (БС).
Это первый метод сортировки, который будет определен рекурсивно. Процесс быстрой сортировки состоит с следующем: мы берем аы первый элемент списка данных, затем каждый элемент (исключая аг) помещаем слева от аы если он меньше или равен аы Назовем этот список 5ы Затем поместим справа от аг каждый элемент, который больше а,. Назовем этот список 5з. Теперь применим этот же процесс к Я1 и Яз. Процесс продолжаем до тех пор, пока в каждом списке не останется по одному элементу. Затем собираем новый список, каждый раз производя конкатенацию Я„а„Я,~1 в список Я,а,Я,.г,, где а, — элемент, который послужил основой для создания Я, и 5,~ы Более формально алгоритм описывается следующим образом; Процедура БС(1, и): Положить 1 = 1 и г = и; Если 1ф г, то Положить т = ( и разбить список (аца~+ыаььз,...,а„) на Ви полученный как (а,: а; < ап 1 ф(), и Яз, полученный как (а,: а, > ап ), так что 51 —— (ам а~<.ма~~.з,...,а,) и Яг = (а..гыауез,а,.ьз,..., а,.) после переобозначения; Произвести конкатенацию БС(1,1), а„, и БС(1+ 1, г); Конец процедуры.
ПРИМЕР $.29. Пусть, как и ранее, а, Ь,с,г,о,й,а — список для сортировки. Поскольку а — первый элемент списка, разбиваем список на два подсписка: Ь,с,а— элементов, меньших а, и г,е,6 — список элементов, больших г(. Далее, согласно процедуре БС первым рассматриваем левый из вновь созданных подсписков, там мы используем Ь для разделения с и а на списки, где а будет слева, а с— справа. После конкатенации получаем а, Ь,с и возвращаемся к первому шагу, где процедура БС вызывается для списка справа от а, а именно, г,е, Ь.
Буква г используется для разделения о и Ь в списки Ь и и. После конкатенации имеем Ь,г,е. И, наконец, последняя конкатенация дает список а,Ь,с,а,п,г,е. П Теперь оценим количество операций сравнения, используемых в этом процессе. Быстрая сортировка реализуется наиболее оптимально, когда и = 2 для некоторого гп, и каждое разбиение делит список элементов ровно пополам. Предположим, что это так.
Если Я„ — число сравнений в быстрой сортировке для списка из и элементов, тогда имеется п операций сравнения для определения, в какой из списков попадет тот или иной элемент. Далее будет уже два списка РАЗДЕЛ 5.4. Алгоритмы сортировки 209 оставшихся п — 2 элементов, каждый из которых потребует Я- операций сравнения, поэтому Я„= 2Я- + п. Но и = 2, так что СС = Яг = 29г — +2 Поэтому Яг 2 Яг -г Яг 2п~ +1+1= — г Яг-- 2т-г 2 +т =Яг+т. Поскольку п = 2, то т = 1окг(п), поэтому Я„= пег + 1окг(и)), что приблизительно равно и 1п(и).
Таким образом, число сравнений имеет порядок О(п!окг(п)). Самый неблагоприятный случай и наибольшее число операций сравнения реализуются, когда элемент, который обычно разделяет множество элементов, всегда остается в конце списка. В этом случае число операций сравнения совпадает с тем, которое требуется в рассмотренных ранее алгоритмах сортировки, поэтому в самом неблагоприятном случае число сравнений имеет порядок О(пг). Аналогичной, но более простой для понимания процедурой, является сортировка слиянием (СС). Процедура состоит в разделении элементов, подлежащих сортировке, пополам или почти пополам. Затем каждый из списков опять делится пополам. Процесс продолжается до тех пор, пока каждое множество не будет содержать только один элемент.
После этого процесс обращается, списки собираются вместе таким же способом, как они разделялись, но при этом происходит их слияние. Сначала мы опишем собственно процедуру сортировки слиянием, а затем приведем пример, иллюстрирующий, как ее применять. В большинстве случаев, использующих рекурсию, процедура вызывает себя через свое имя в теле процедуры. Чтобы явно указать тот факт, что процедура вызывает сама себя, мы будем использовать команду "вызов". В приведенной процедуре переменные 1, гп и г представляют левый, центральный и правый элементы в текущем списке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
