Лекция 12. Быстрая сортировка. Рекурсия (Электронные лекции)

Лекции по курсу “Алгоритмы и алгоритмические языки”, 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, имеет вид1T (n) =  T (1) + T (n − 1) +n + Θ ( n) .(T(q)+T(n−q))∑q= 1n− 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.