Лекция 12. Быстрая сортировка. Рекурсия (1107987)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекция 12 Быстрая сортировка12.1. QuickSort: программа на Си.12.1.1. QuickSort – рекурсивная Си-функция следующего вида:/* Быстрая сортировка. Предполагается, что left < right */void QuickSort (int *a, int left, int right) {/* comp – компаранд, i, j – значения индексов элементовмассива a */int comp, tmp, i, j;/* выбор компаранда */i = left; j = right;comp = a[(left + right)/2]; //можно и a[left] или a[right]/* построение Partition – цикл do-while */do {while((a[i] < comp) && (i < right)) i++;while((comp < a[j]) && (j > left)) j--;if (i <= j) {tmp = a[i];a[i] = a[j];a[j] = tmp;i++; j--;}} while(i < j);/* продолжение сортировки, если не все отсортировано */if(left < j)QuickSort (*a, left, i - 1);if(i < right)QuickSort (*a, j + 1, right);}12.1.2.
Программа быстрой сортировки.void qsort (int *a, int n) {QuickSort (*a, 0, n-1);}12.1.3. Цикл do-while (или do). В отличие от цикла while сначала выполняется телоцикла, а потом проверяется условие выхода из цикла. В рассматриваемой программеэто do {〈тело цикла〉} while(i <= j);12.1.4. Объяснение работы программы на рисунке: массив a[] и его индексы.Покажем, что цикл do-while действительно строит нужное нам разбиение массиваa[].(1) В процессе работы цикла индексы i и j не выходят за пределы отрезка [left, right],так как в циклах while выполняются соответствующие проверки.(2) В момент окончания работы цикла do-while j ≤ right, так как части разбиенияне могут быть пустыми: хотя бы один элемент массива a[] (в крайнем случаеa[right]) содержится в правой части разбиения. Аналогично, в моментокончания работы цикла do-while i ≥ left.(с) Кафедра системного программирования ф-та ВМК МГУ, 20101Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год(3) В момент окончания работы цикла do-while любой элемент подмассиваa[left..k-1] не больше любого элемента подмассива a[k+1..
right] ,где k – индекс компаранда, что очевидно.12.1.5. Работа цикла do-while на примере: 5 3 2 6 4 1 3 7. Пусть в качестве первогокомпаранда выбран первый элемент массива – 5 (a[left]). Во время первогопрохода цикла do-while после выполнения обоих циклов while получим:(5) 3 2 6 4 1 {3} 7;(в круглых скобках элемент с индексом i, в фигурных – элемент с индексом j).Поскольку i < j, элементы, выделенные скобками, нужно поменять местами(оператор if): 3 (3) 2 6 4 1 {5} 7; (выделены уже сформировавшиеся кускимассива a). В результате второго прохода цикла do-while получим: до переменымест 3 3 2 (6) 4 {1} 5 7; а после обмена 3 3 2 1 (4) {6} 5 7; Теперьмассив a состоит из двух подмассивов 3 3 2 1 4 и 6 5 7 причем i < j (i = 5, j =6).
Теперь нужно применить метод к этим подмассивам (рекурсивные вызовы).12.1.6. При выборе компаранда можно брать первый элемент, значение которого большезначения следующего элемента. Для результирующих подмассивов из п.°12.1.5компаранды заключены в квадратные скобки: 3 [3] 2 1 4; [6] 5 7.12.2. Оценка времени выполнения алгоритма QuickSort.12.2.1. Время выполнения цикла do-while Θ(n), где n = right – left +1.Замечание. Если f(n) и g(n) – некоторые функции, то запись g(n) = Θ(f(n)) означает,что найдутся такие константы c1, c2 >0 и такое n0, что для всех n ≥ n0 выполняютсясоотношения 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n). Иными словами при больших n f(n) хорошоописывает поведение g(n).
Наше утверждение означает, что неизвестная функцияtPart(n) (время построения Partition) ведет себя как c⋅n, где c – положительнаяконстанта.12.2.2. Можно доказать, что для алгоритма QuickSort максимальное (наихудшее) времявыполнения Tmax(n) = Θ(n2). Наихудшее время получается, когда при каждомPartition массив длины n разбивается на подмассивы длины 1 и n – 1. В самом деле,для Tmax(n) имеет место соотношение Tmax(n) = Tmax(n – 1) + Θ(n).
Очевидно, что Tmax(1)= Θ(1). Следовательно,nTmax(n) = Tmax(n – 1) + Θ(n) =∑k=1nΘ (k ) = Θ (∑ k ) = n⋅(n – 1)/2 = Θ(n2).k= 1В частности, если исходный массив a отсортирован в порядке убывания, время егосортировки в порядке возрастания с помощью алгоритма QuickSort будет Θ(n2).12.2.3. Минимальное и среднее время выполнения алгоритма QuickSort Tmean(n) = Θ(n⋅log n) сразными константами: чем ближе разбиение на подмассивы к сбалансированному,тем константы меньше. Доказательство использует теорему о рекуррентныхоценках 112.2.4.
Рекуррентное соотношение для минимального (наилучшего) времени сортировкиTmin(n) имеет видTmin(n) = 2⋅Tmin(n/2) + Θ(n),так как минимальное время получается тогда, когда на каждом шаге удается выбратькомпаранд, который делит массив на два подмассива одинаковой длины n/2.Применяя ту же теорему, получаем Tmin(n) = Θ(n⋅log n).1Т. Кормен, Ч. Лейзерсон, Р.
Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. ISBN 5-900916-37-5, с. 66 –73.(с) Кафедра системного программирования ф-та ВМК МГУ, 20102Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год12.2.5. Рекуррентное соотношение для (n) в общем случае, когда на каждом шаге массивделится в отношении q:(n – q), причем q с вероятностью 2/ принимает значение 1 и свероятностями 1/n значения 2, …, n – 1, имеет вид1T (n) = T (1) + T (n − 1) +n + Θ ( n) .(T(q)+T(n−q))∑q= 1n− 1Достаточно сложные рассуждения позволяют решить это соотношение и установить,что T(n) = Θ(n⋅log n) (та же книга, с.160 – 164).12.2.6.
Более того, упомянутые методы позволяют доказать, что не существует алгоритмасортировки массива из n элементов,12.3. Как в системе программирования Си выполняются рекурсивные функции?12.3.1. В Си разрешается, чтобы функция вызывала сама себя. Такая функция называетсярекурсивной. QuickSort – пример рекурсивной функции. Более простой пример –рекурсивная функция, вычисляющая числа Фибоначчи.12.3.2. Числа Фибоначчи возникли в решении задачи о кроликах, предложенном в XIII векеЛеонардо из Пизы, известным как Фибоначчи.
Задача: пара новорожденныхкроликов помещена на остров. Каждый месяц любая пара дает приплод – также парукроликов. Пара начинает давать приплод в возрасте двух месяцев. Сколько кроликовбудет на острове через n месяцев? В конце первого и второго месяцев на островебудет одна пара кроликов: f1 = 1, f2 = 1. В конце третьего месяца родится новая пара,так что f3 = f2 + f1. По индукции можно доказать, что для n ≥ 3 fn = fn-1 + fn-2.Рекурсивная программа:/* Вычисление n–го числа Фибоначчи */int Fib(int n) {if (n < 1)return (0) // неверные начальные данныеif ((n == 1) || (n == 2))return 1;elsereturn (Fib(n – 1) + Fib (n – 2));}12.3.3. Рекурсивная функция выполняется сложнее, чем не рекурсивная.
Пусть, например, n= 4. Вызов Fib(4) приведет к вызову Fib(3) и Fib(2), вызов Fib(3) – квызову Fib(2) и Fib(1). При каждом вызове будет выполняться одна и та жефункция, но над разными данными (копий кода функции не создается). Данныеразмещаются в стеке как показано на рисунке.(с) Кафедра системного программирования ф-та ВМК МГУ, 20103Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годДанные Fib(1)Данные Fib(2)Данные Fib(2)Данные Fib(3)Данные Fib(4)Дно стека12.3.4. Не рекурсивная программа (в большинстве случаев рекурсию нетрудно заменитьитерацией).int Fbn(int n) {if ((n == 1) || (n == 2))return 1;else {g = h = 1;for(k = 2; k < n; k++) {Fb = g + h;h = g;g = Fb;}return Fb;}}(с) Кафедра системного программирования ф-та ВМК МГУ, 20104.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
