Отчет по практике: Информатика. Текстовый редактор

соответственно меньших, равных и больших а;

3. return(БЫСТРСОРТ(S1), затем S2, затем БЫСТРСОРТ (S3))

end

Рисунок 3.7. Программа Быстрсорт.

Алгоритм 3.5. Быстрсорт

Вход. Последовательность S из n элементов a_ь a₂ , ... , a_п .

Выход. Элементы последовательности S, расположенные по порядку.

Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове БЫСТРСОРТ(S).

Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из п элементов за среднее время О (п logп).

Доказательство. Корректность алгоритма 3.5 доказы­вается прямой индукцией по длине последовательности S. Чтобы проще было анализировать время работы, допустим, что все элементы в S различны. Это допущение максимизирует размеры последова­тельностей S1 и S3, которые строятся в строке 3, и тем самым мак­симизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (n) — среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из n элементов. Ясно, что Т(0)=Т(1)=b для некоторой постоянной b.

Допустим, что элемент а, выбираемый в строке 2, является 1-м наименьшим элементом среди n элементов последовательности S. Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время Т(i - 1) и Т (n - i) соответственно. Так как i равно­вероятно принимает любое значение между 1 и n, а итоговое по­строение последовательности БЫСТРООРТ(S) очевидно занимает время cn для некоторой постоянной с, то

T(n)cn+[T(i-1)+T(n-1)] дляn2 (3.3)

Алгебраические преобразования в (3.3) приводят к неравенству

T(n)cn+T(i) (3.4)

Покажем, что при n2 справедливо неравенство Т (n)<kn 1nn, где k=2с+2b и b=Т(0)=T(1). Для базиса (n=2) неравенство Т(2)2с+2b непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в виде

T(n)cn + + kilni (3.5)

Так как функция ilni вогнута, легко показать, что

i ln i x ln x dx (3.6)

Подставляя (3.6) в (3.5), получаем

T(n)cn + + knlnn -

Поскольку n2 и k=2с+2b, то сn+4 b/nkn/2. Таким образом, неравенство Т (n)kn1nn следует из (3.7).

Рассмотрим две детали, важные для практической реализации алгоритма. Первая — способ "произвольного" выбора элемента а в строке 2 процедуры БЫСТРСОРТ. При реализации этого опера­тора может возникнуть искушение встать на простой путь, а именно всегда выбирать, скажем, первый элемент последовательности S. Подобный выбор мог бы оказаться причиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из (3.3). После­довательность, к которой применяется подпрограмма сортировки, часто бывает уже "как-то" рассортирована, так что первый элемент мал с вероятностью выше средней. Читатель может проверить, что в крайнем случае, когда БЫСТРСОРТ начинает работу на уже упо­рядоченной последовательности без повторений, а в качестве эле­мента а всегда выбирается первый элемент из S, в последователь­ности S всегда будет на один элемент меньше, чем в той, из которой она строится. В этом случае БЫСТРСОРТ требует квадратичного числа шагов.

Лучшей техникой для выбора разбивающего элемента в строке 2 было бы использование генератора случайных чисел для порожде­ния целого числа i, 1<i<|S| ¹ ), и выбора затем i-го элемента из S в качестве а. Более простой подход — произвести выборку элемен­тов из S, а затем взять ее медиану в качестве разбивающего элемен­та. Например, в качестве разбивающего элемента можно было бы взять медиану выборки, состоящей из первого, среднего и послед­него элементов последовательности S.

Вторая деталь — как эффективно разбить S на три последова­тельности S1, S2 и S3? Можно (и желательно) иметь в массиве А все n исходных элементов. Так как процедура БЫСТРСОРТ вызы­вает себя рекурсивно, ее аргумент S всегда будет находиться в по­следовательных компонентах массива, скажем A[f], A[f+1], ..., A[l] для некоторых f и l, 1<f<n. Выбрав "произвольный" элемент а, можно устроить разбиение последовательности S на этом же месте. Иными словами, можно расположить S1 в компонентах A[f], A[f+1], ... A[k], а S2S3— в A[k+1], A[k+2], ..., A[l] при некотором k, fklЗатем можно, если нужно, расщепить S2S3, но обычно эффективнее просто рекурсивно вызвать БЫСТР­СОРТ на S1 и S2S3, если оба этих множества не пусты.

По-видимому, самый легкий способ разбить S на том же месте — это использовать два указателя на массив, назовем их i и j. Вначале

1. begin

2. if;

3. while ijdo

begin