Алгоритм быстрой сортировки

Министерство образования республики Беларусь УО «Мозырский государственный университет имени И. П. Шамякина»

Кафедра информатики и методики преподавания информатики Курсовая работа Алгоритм быстрой сортировки Выполнила:

студентка 3 курса 1 группы физико-математического факультета Савенко Елена Николаевна Научный руководитель:

Доцент кафедры информатики и методики преподавания информатики, кандидат физико — математических наук Сергиевич Николай Владимирович Мозырь 2007

• Введение
• Глава 1. Основные теоретические аспекты алгоритма и сортировки
• 1.1 Понятие алгоритма и сортировки
• 1.2 Основные способы и алгоритмы сортировки массивов
• 1.3 Быстрая сортировка Хоара
• 1.4 Основные правила, понятия и теоремы
• 1.5 Псевдокод
• Глава 2. Реализация алгоритма «быстрой сортировки»
• 2.1 Описание алгоритма «быстрой сортировки»
• 2.2 Реализация на языке программирования
• Глава 3. Анализ быстрой сортировки
• 3.1Анализ наихудшего разбиения
• 3.2 Наилучшее разбиение
• 3.3Промежуточный случай
• 3.4 Вероятностные алгоритмы быстрой сортировки
• 3.5 Нахождение и анализ среднего времени работы сортировки
• 3.5.1 Интуитивные соображения по нахождению среднего времени
• 3.5.2 Анализ среднего времени работы
• Введение
• В последние годы программирование для вычислительных машин стало не только средством, владение которым оказывается решающим для успешной работы во многих прикладных областях, а так же и предметом научного изучения. Стало ясно, что решение о структурировании данных нельзя принимать без знания алгоритмов. Так же с каждым годом жизнь становится все быстрее и быстрее, ускоряется и увеличивается поток информации. Для хранения всевозможной информации применяются так называемые базы данных. Но и с этими базами, особенно если они содержат миллионы пунктов, работать достаточно сложно, можно даже сказать невозможно. Разобраться в таком количестве данных без сортировки практически не возможно, они позволяют относительно быстро и качественно выделить необходимую информацию из предварительно упорядоченного набора. Следовательно, методы сортировки очень важны, особенно при обработке данных. В программировании уделяется огромное внимание сортировкам и их алгоритмам.
• В настоящее время существует огромное множество алгоритмов сортировки, которые имеют различный характер и скорость обработки информации. Однако многие из них обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а, начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике.
• В данной курсовой работе будем рассматривать одну из лучших сортировок. Которая носит название быстрая сортировка, алгоритм которой признан наилучшим.
• Целью курсовой работы является изучение современных технологий программирования и анализ алгоритма быстрой сортировки Хоара.
• Задачи курсовой работы:
• 1. изучить теоретическую основу алгоритмов сортировки;
• 2. рассмотреть алгоритм быстрой сортировки Хоара;
• 3. реализовать его на языке программирования;
• 4. произвести анализ работы сортировки.

Глава 1. Основные теоретические аспекты алгоритма и сортировки

1.1 Понятие алгоритма и сортировки

Алгоритм (algorithm) — это любая корректно определенная вычислительная процедура, на вход (input), которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные.

Алгоритм также можно рассматривать как инструмент, предназначенный для решения корректно поставленной вычислительной задачи. В алгоритме описывается конкретная вычислительная процедура, с помощью которой удается добиться выполнения указанных отношений.

Например, может понадобиться выполнить сортировку последовательности чисел в неубывающем порядке. Эта задача часто возникает на практике и служит благодатной почвой для ознакомления на ее примере со многими стандартными методами разработки и анализа алгоритмов.

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список L из n элементов будет отсортирован в порядке возрастания значений элементов, если L1 <= L2 <= … <= Ln.

Цель сортировки — облегчить поиск элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонной книге, в оглавлениях, в библиотеках, в словарях, да почти всюду. Даже маленьких детей приучают привадить вещи «в порядок», и они сталкиваются с некоторым видом сортировки за долго до того, как узнают что-либо об арифметике.

Если речь идет о задаче сортировки, обычно предполагается, что входные данные состоят только из чисел. Преобразование алгоритма, предназначенного для сортировки чисел, в программу для сортировки записей не представляет трудностей, хотя в практической ситуации иногда возникают различные тонкие нюансы, усложняющие задачу программиста.

Зависимость выбора алгоритмов от структуры данных — явление довольно частое, особенно при обработке данных, и в случае сортировки она настолько сильна, что методы сортировки подразделяют на два вида: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.

Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.

1.2 Основные способы и алгоритмы сортировки массивов

В этой курсовой работе будет рассмотрена только сортировку массивов, которая имеет три основных способа:

· сортировка обменом;

· сортировка выбором;

· сортировка вставкой.

Пусть на столе лежит колода карт. Для сортировки обменом их необходимо разложить лицевой стороной вверх и затем менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.

Для сортировки выбором вы должны разложить карты на столе, выбрать самую младшую карту и взять ее в свою руку. Затем вы должны из оставшихся на столе карт вновь выбрать наименьшую по значению карту и поместить ее позади той карты, которая уже имеется у вас в руке.

Этот процесс вы должны продолжать до тех пор, пока все карты не окажутся у вас в руках. Поскольку каждый раз вы выбираете наименьшую по значению карту из оставшихся на столе, по завершению такого процесса карты у вас в руке будут отсортированы.

Для сортировки вставкой вы должны держать карты в своей руке, поочередно снимая карту с колоды. Каждая взятая вами карта помещается в новую колоду на столе, причем она ставится на соответствующее место. Колода будет отсортирована, когда у вас в руке не окажется ни одной карты.

Для каждого способа сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки зависит от ответов, которые будут получены на следующие вопросы:

· с какой средней скоростью этот алгоритм сортирует информацию?;

· какова скорость для лучшего случая и для худшего случая?;

· поведение алгоритма является естественным или является не естественным?;

· выполняется ли перестановка элементов для одинаковых ключей?

Для алгоритма большое значение имеет скорость сортировки. Скорость, с которой массив может быть упорядочен, прямо зависит от числа сравнений и числа необходимых операций обмена, причем операции обмена занимают большое время.

Время работы алгоритма для лучшего и худшего случаев важно учитывать, когда ожидается их частое появление. Часто сортировка имеет хорошую среднюю скорость, но очень плохую скорость для худшего случая, и наоборот.

Считается поведение алгоритма сортировки естественным, если время сортировки наименьшее при упорядоченном списке элементов, время сортировки увеличивается при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке. Время сортировки зависит от числа операций сравнения и операций обмена.

В информатике сортировка является основополагающей операцией (во многих программах она используется в качестве промежуточного шага), в результате чего появилось большое количество хороших алгоритмов сортировки. Выбор наиболее подходящего алгоритма зависит от многих факторов, в том числе от количества сортируемых элементов, от их порядка во входной последовательности, от возможных ограничений, накладываемых на члены последовательности, а также от того, какое устройство используется для хранения последовательности: основная память, магнитные диски или накопители на магнитных лентах.

Наиболее известной (и наиболее «бесславной») является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.

При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т. д. до обмена двух последних элементов.

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

1.3 Быстрая сортировка Хоара

Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а, начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике. Каждый программист слышал или рассказывал «страшные» истории о «сортировке, которая выполнялась три дня». К сожалению, эти истории часто не являлись выдумкой.

Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Однако первая реакция на такое поведение сортировки выражается словами: «Давай напишем программу на ассемблере». Хотя использование ассемблера почти всегда позволяет повысить быстродействие программы в некоторое число раз с постоянным коэффициентом, но если выбранный алгоритм не является достаточно хорошим, то сортировка вне зависимости от оптимальности кода по-прежнему будет выполняться долго. Следует помнить, что при квадратичной зависимости времени выполнения программы от числа элементов массива повышение оптимальности кода или повышение быстродействия ЭВМ приведет лишь к незначительному улучшению, поскольку время выполнения программы будет увеличиваться по экспоненте. Следует помнить, что если какая-либо программа, написанная на языке Паскаль, выполняется недостаточно быстро, то она не станет выполняться достаточно быстро, если ее написать на ассемблере. Решение лежит в использовании лучшего алгоритма сортировки.

В этой работе будет рассмотрена одна очень хорошая сортировка. Которая носит название быстрая сортировка, алгоритм которой признан наилучшим. Эта сортировка выполняются очень быстро.

Метод быстрой сортировки был разработан в 1960 году Ч.Ф. Р. Хоаром (C.A.R.Hoare) и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.

В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве «основы» и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие «основы», а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован. Например, для массива «7 356 821 «при использовании в качестве значения разбиения «5» будут получены следующие проходы при выполнении быстрой сортировки:

исходное состояние: 7 356 821;

первый проход: 2 135 687;

второй проход: 1 235 678.

Этот процесс продолжается для каждой части «2135» и «687». Фактически этот процесс имеет рекурсивную природу. И действительно, наиболее «аккуратно» быстрая сортировка реализуется посредством рекурсивного алгоритма.

Однако следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n. Однако на практике этот случай не встречается.

1.4 Основные правила, понятия и теоремы

Рекуррентные соотношения.

Для определения времени работы алгоритма, используются так называемые рекуррентные соотношения Получение рекуррентного соотношения для времени работы алгоритма, основанного на принципе «разделяй и властвуй», базируется на трех этапах.

Обозначим через T (n) время решения задачи, размер которой равен n. Если размер задачи достаточно мал, скажем, n? с, где с — некоторая заранее известная константа, то задача решается непосредственно в течение определенного фиксированного времени, которое мы обозначим через ?(1). Предположим, что наша задача делится на a подзадач, объем каждой из которых равен 1/b от объема исходной задачи. Если разбиение задачи на вспомогательные подзадачи происходит в течение времени D (n), а объединение решений подзадач в решение исходной задачи — в течение времени С (n), то мы получим такое рекуррентное соотношение:

Основной метод решения рекуррентных отношений базируется на основной теореме, приведенной ниже.

Теорема 1.

Пусть и — константы, — произвольная функция, а — произвольная функция, определенная на множестве неотрицательных целых чисел с помощью рекуррентного соотношения

Тогда асимптотическое поведение функции можно выразить следующим образом.

1. Если для некоторой константы, то .

2. Если, то .

3. Если для некоторой константы, и если для некоторой константы и всех достаточно больших n, то .

Правило 1. Арифметическая прогрессия.

Сумма

является арифметической прогрессией и ее значение равно:

.

Правило 2. Разбиение на части.

Можно разбить сумму на части и оценивать их по отдельности. В качестве примера возьмем сумму. Получим

.

1.5 Псевдокод

Перечислим основные соглашения, которые мы будем использовать.

· Отступ от левого поля указывает на уровень вложенности.

· Циклы while, for, repeat и условные конструкции if, then, else имеют тот же смысл, что и в Паскале.

· Символ > начинает комментарий (идущий до конца строки).

· Одновременное присваивание (переменные и получают значение) заменяет два присваивания и (в этом порядке).

· Переменные локальны внутри процедуры (если не оговорено противное).

· Индекс массива пишется в квадратных скобках: есть — й элемент в массиве. Знак «.» выделяет часть массива: обозначает участок массива, включающий .

· Часто используются объекты, состоящие из нескольких полей, или, как говорят, имеющие несколько атрибутов. Значение поля записывается как имя_поля [имя_объекта]. Например, длина массива считается его атрибутам и обозначается length, так что длина массива запишется как length. Из контекста обычно ясно, что именно обозначают квадратные скобки (элемент массива или поле объекта).

Переменная, обозначающая объект или массив, считается указателем на составляющие его данные. После присваивания для любого поля выполнено .

· Параметры передаются по значению: вызванная процедура получает собственную копию параметров; изменение параметра внутри процедуры снаружи невидимо. При передаче объектов копируется указатель на данные составляющие этот объект, а сами поля объекта — нет.

Глава 2. Реализация алгоритма «быстрой сортировки»

В этой главе мы рассмотрим сам алгоритм «быстрой сортировки» и процедуру разбиения массива на части. Также реализуем его на языке программирования.

2.1 Описание алгоритма «быстрой сортировки»

Быстрая сортировка (quicksort), как и сортировка слиянием, по своей природе рекурсивна, т. е. она для решения некоторой задачи вызывает саму себя для решения её подзадач; и основана на принципе «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти подзадачи решаются. И наконец, их решения комбинируются и получается решение исходной задачи.

Сортировка участка, А [p.r] происходит так:

· Элементы массива, А переставляются так, чтобы любой из элементов А[р]…А[q] был не больше любого из элементов, А [q+1]…A[r], где q — некоторое число в интервале р=

· Процедура сортировки рекурсивно вызывается для массивов A[p.q] и A[q+l.r].

После этого массив, А [р…r] отсортирован.

Итак, процедура сортировки QUICKSORT выглядит следующим образом:

Quicksort (p, r)

1. если p

3. Quicksort (p, q)

4. Quicksort (q+ 1, r)

Ключевой частью рассматриваемого алгоритма сортировки является функция Part, изменяющая порядок элементов массива, А [р.r] без привлечения дополнительной памяти.

Выбираем элемент x=А [р] в качестве «граничного»; массив, А [р.q] будет содержать элементы, не большие х. А массив A [q+l.r] — элементы, не меньшие х. Идея состоит в том, чтобы накапливать элементы, не большие х, в начальном отрезке массива A[p.i], а элементы, не меньшие х — в конце A[j.r]. В начале оба «накопителя» пусты: i = р-1, j = r + 1:

i < p-1;

j

x

Создадим цикл, в котором найдем элементы виде A[j]<=x и A[i]>=x. Для этого мы будем уменьшать j пока A[j]<=x и увеличивать i пока A[i]>=x. Затем, сравнивая i и j, посмотри, где находятся наши элементы в массиве A[p.i] или в массиве A[j.r]. Затем проверим выполняется ли неравенство i

Хотя идея функции очень проста, сам алгоритм содержит ряд тонких моментов. Например, не очевидно, что индексы i и j не выходят за границы промежутка [р.r] в процессе работы. Другой пример: важно, что в качестве граничного значения выбирается, А [р], а не, скажем, A[r]. В последнем случае может оказаться, что A[r] - самый большой элемент массива, и в конце выполнения процедуры будет i=j=r, так что возвращать j функции будет нельзя — нарушится требование q < r, и процедура Quicksort зациклится.

Время работы функции Part составляет, где .

2.2 Реализация на языке программирования

Мы рассмотрели алгоритм «быстрой сортировки», который описали на повседневном языке, понятном почти всем. А для реализации данного алгоритма был выбран язык программирования Pascal. Причина такого выбора заключается в том, что он был изначально разработан в учебных целях, прост и эффективен. Перевод программы на язык программирования подразумевает довольно глубокие знания того языка, на котором пишется программа. Вот еще одна причина, по которой был выбран язык Pascal.

Рассмотрим базовые процедуры и функции, которые использовались при написании программы.

Процедуры read и write используются для ввода и вывода данных.

Reset — процедура, открывающая файл для чтения.

Assign — процедура, предназначенная для связывания файловой переменной с файлом на диске.

Rewrite — процедура, открывающая файл для записи. Если файла не существует, то она создает его.

Close — процедура, закрывающая открытый файл.

Теперь мы рассмотрим более подробно структуру программы. В первую очередь назовем программу «Q123». Затем введем константу, которая определяет величину массива (в нашем случае n=10). Так же нам необходимо описать переменные и сам массив, которые будут использоваться в данной программе:

var

k:integer;

A:array [1.n] of integer;

Для ввода массива создадим специальный файл «input.txt», в который будем вводить сам массив. Например: 5 4 2 9 6 1 4 2 9 5. И файл, в который будем выводить отсортированный массив «output.txt».

assign (input,'input.txt'); reset (input);

assign (output,'output.txt'); rewrite (output);

С помощью оператора For прочтем массив из файла.

for k:=1 to n do read (A[k]);

Теперь мы опишем саму процедуру Quicksort, которая также будет включать свои переменные.

procedure QuickSort (p, r: integer);

var q: integer;

Эта переменная будет являться тем средним значением, которое мы получим в результате функции Part (ее опишем ниже). Затем процедура Quicksort вызывает саму себя уже для подмассивов [р.q] и [q+l.r].

Но это все будет выполняться, если будет выполняться условие p

if p

q:=Part (p, r);

QuickSort (p, q);

QuickSort (q+1,r);

end;

В этой процедуре используется функция Part, которая так же имеет свои переменные:

function Part (p, r: integer):integer;

var c, x, j, i, q:integer;

Эта функция сортирует массив с помощью нескольких операторов. Но для начала нам необходимо ввести два накопителя, которые сразу пусты. И введем некоторое значение x.

i:=p-1;

j:=r+1;

x:=A[p];

С помощью оператора while мы будем повторять следующие действия.

while true do begin

И так, для начала мы будем уменьшать j, пока A[j]>=x:

repeat

j:=j-1

until A[j]<=x;

И увеличивать i, пока A[i]>=x:

repeat

i:=i+1

until A[i]>=x;

Проверим условие i

if (i

c:=A[i];

A[i]:=A[j];

A[j]:=c;

end

else break;

После этого мы присваиваем значение j самой функции Part.

В конце самой программы мы выводим отсортированный массив в раннее созданный файл «output.txt». Всю программу можно увидеть в приложении 1.

Глава 3. Анализ быстрой сортировки

Анализ алгоритма заключается в том, чтобы предсказать требуемые для его выполнения ресурсы. Иногда оценивается потребность в таких ресурсах, как память, пропускная способность сети или необходимое аппаратное обеспечение, но чаще всего определяется время вычисления. Путем анализа нескольких алгоритмов, предназначенных для решения одной и той же задачи, можно без труда выбрать наиболее эффективный. Но нам необходимо сделать анализ только одного алгоритма быстрой сортировки.

3.1 Анализ наихудшего разбиения

«Наиболее неравные части» получатся, если одна часть содержит n — 1 элемент, а вторая — всего 1. Предположим, что на каждом шаге происходит именно так. Поскольку функция разбиения занимает время, для времени работы получаем соотношение:

.

Поскольку, имеем:

(последняя сумма — арифметическая прогрессия, см. правило 1). Дерево рекурсии для этого случая показано на рис. 1.

Рис.1

Мы видим, что при максимально несбалансированном разбиении время работы составляет, как и для сортировки вставками. В частности, это происходит, если массив изначально отсортирован. Интуитивно видно, что этот случай является наихудшим. А теперь мы это строго докажем.

Для доказательства того, что время работы составляет, мы используем метод подстановки (смотри правило 3). Пусть — наибольшее время работы алгоритма для массива длины n. Тогда, очевидно

.

В этой формуле мы рассмотрели все возможные разбиения на первом шаге. Предположим, что для некоторой константы с и для всех q, меньших не которого n. Тогда

.

Квадратный трёхчлен достигает максимума на отрезке в его концах, т. к. вторая производная по q положительна и функция выпукла вниз. Этот максимум равен. Отсюда получаем

,

если константа с выбрана так, чтобы последнее слагаемое было меньше предпоследнего. Итак, время работы в худшем случае составляет .

3.2 Наилучшее разбиение

алгоритм сортировка хоар программирование

Если на каждом шаге массив разбивается ровно пополам, быстрая сортировка требует значительно меньше времени. Действительно, в этом случае рекуррентное соотношение имеет вид

и, согласно теореме 1,. Дерево рекурсии для этого случая показано на рисунке 2.

Рис.2

3.3 Промежуточный случай

Предположим, что среднее время работы (с точностью до множителя) совпадает со временем работы в наилучшем случае. Чтобы объяснить это, посмотрим, как меняется рекуррентное соотношение в зависимости, от степени сбалансированности разбиения.

Пусть, например, на каждом шаге массив разбивается на две части с отношением размеров 9:1. Тогда

(для удобства мы заменили на). Дерево рекурсии показано на рисунке 3. На каждом уровне мы производим не более n действии, так что время работы определяется глубиной рекурсии.

В данном случае эта глубина равна, так что время работы по-прежнему составляет ?(nlgn), хотя константа и больше. Ясно, что для любого фиксированного отношения размеров частей (сколь бы велико оно ни было) глубина дерева рекурсии по-прежнему будет логарифмической, а время работы будет равно ?(nlgn).

Рис. 3.

3.4 Вероятностные алгоритмы быстрой сортировки

Ранее мы предположили, что все перестановки входных значений равновероятны. Если это так, а размер массива достаточно велик, быстрая сортировка — один из наиболее эффективных алгоритмов. На практике, однако, это предположение не всегда оправдано.

Теперь мы введём понятие вероятностного алгоритма и рассмотрим два вероятностных алгоритма быстрой сортировки, которые позволяют отказаться от предположения о равной вероятности всех перестановок.

Идея состоит в привнесении случайности, обеспечивающем нужное распределение. Например, перед началом сортировки можно случайно переставить элементы, после чего уже все перестановки станут равновероятными (это можно сделать за время О (n)). Такая модификация не увеличивает существенно время работы, но теперь математическое ожидание времени работы не зависит от порядка элементов во входном массиве (они всё равно случайно переставляются).

Алгоритм называется вероятностным (randomized), если он использует генератор случайных чисел (random-number generator). Мы будем считать, что генератор случайных чисел Random работает так: RANDOM (a, b) возвращает с равной вероятностью любое целое число в интервале от, а до b. Например. Random (0,1) возвращает 0 или 1 с вероятностью ½. При этом разные вызовы процедуры независимы в смысле теории вероятностей. Для такого вероятностного варианта алгоритма быстрой сортировки нет «неудобных входов»: т.к. количество перестановок, при которых время работы велико, совсем мало — поэтому вероятность того, что алгоритм будет работать долго невелика.

Аналогичный подход применим и в других ситуациях, когда в ходе выполнения алгоритма мы должны выбрать один из многих вариантов его продолжения, причём мы не знаем, какие из них хорошие, а какие плохие, но знаем, что хороших вариантов достаточно много. Нужно только, чтобы плохие выборы не разрушали достигнутого при предыдущих хороших.

Вместо того, чтобы предварительно переставлять элементы массива, мы можем внести элемент случайности в функцию Part. Именно, перед разбиением массива, А [p.r] будем менять элемент А[р] со случайно выбранным элементом массива. Тогда каждый элемент с равной вероятностью может оказаться граничным, и в среднем разбиения будут получаться достаточно сбалансированными.

Этот подход заменяет разовую случайную перестановку входов в начале использованием случайных выборов на всём протяжении работы алгоритма. В сущности это то же самое, и оба алгоритма имеют математическое ожидание времени работы O (n lgn), но небольшие технические различия делают анализ нового варианта проще, и именно его мы будем рассматривать далее.

Изменения, которые нужно внести в процедуры, совсем неволики:

Rand-Part (А, р, г)

г <�тRandom (р, г)

поменять А[р] f-> A[i]

return Partition (Л. р, г)

В основной процедуре теперь будет использоваться Randomized-Partition вместо Partition:

Randomized-Quicksort (A, р. г)

1 if р < г

2 then q *- Randomized-Partition (A, p, г)

Randomized-Quicksort (A. p, q)

Randomized-Qijicksort (A, q + 1, r)

3.5 Нахождение и анализ среднего времени работы сортировки

3.5.1 Интуитивные соображения по нахождению среднего времени

Чтобы вопрос о среднем времени работы имел смысл, нужно уточнить, с какой частотой появляются различные входные значения. Как правило, предполагается, что все перестановки входных значений равновероятны.

Для наугад взятого массива разбиения вряд ли будут всё время происходить в одном и том же отношении — скорее всего, часть разбиений будет хорошо сбалансирована, а часть нет, примерно 80 процентов разбиений производятся в отношении не более 9:1.

Будем предполагать для простоты, что на каждом втором уровне все разбиения наихудшие, а на оставшейся половине уровней наилучшие (смотри рис. 4). Поскольку после каждого «хорошего» разбиения размер частей уменьшается вдвое, число «хороших» уровней равно ?(lgn), а поскольку каждый второй уровень «хороший», общее число уровней равно ?(lgn), а время работы — ?(nlgn). Таким образом, плохие уровни не испортили асимптотику времени работы, а лишь увеличили константу, скрытую в асимптотическом обозначении.

Рис. 4. Два уровня плохой (n разбивается на n-1 и 1) и хороший (n-1 разбивается на две равные части).

3.5.2 Анализ среднего времени работы

Анализ разбиений.

Напомним, что перед тем как в функции Rand-Part вызывается функция Part, элемент А[р] переставляется со случайно выбранным элементом массива, А [p.r]. Для простоты мы будем предполагать, что все числа в массиве различны. Хотя оценка среднего времени сохраняется и в том случае, когда в массиве есть одинаковые элементы, получить ее сложнее, и мы этого делать не будем.

Прежде всего, заметим, что значение q, которое возвратит функция Part, зависит только от того, сколько в массиве элементов, не больших x= А[р]. Число таких элементов мы будем называть рангом элемента x и обозначать rank (x). Если n число элементов массива, то, поскольку все элементы имеют равные шансы попасть на место А[р], все значения rank (x), от 1 до n, равновероятны и имеют вероятность 1/n.

Если rank (x)>1. то, как легко видеть, при разбиении левая часть будет содержать rank (x)-1 элементов — в ней окажутся все элементы, меньше x. Если же rank (x)=1, то левая часть будет содержать один элемент. Отсюда следует, что с вероятностью 1/n левая часть будет содержать 2,3,…, n-1 элементов, а с вероятностью 2/n — один элемент.

Рекуррентное соотношение для среднего времени работы.

Обозначим среднее время работы алгоритма Rand-Part для массива из n элементов через. Ясно, что. Время работы состоит из времени работы функции Part, которое составляет, и времени работы для двух массивов размеров и, причем с вероятностью 2/n принимает значения 1 и с вероятностью 1/n значения 2, 3,…, n-1. Поэтому

Слагаемое, соответствующее q=1, входит дважды и поскольку и, имеем

.

Поэтому слагаемые и в первой скобке (1) можно включить в. С учетом этого получаем

.

Поскольку каждое слагаемое, где k=1, 2,…, n-1, встречается в сумме дважды, ее можно переписать так:

.

Решение рекуррентного соотношения.

Соотношение 2 можно решить, используя метод подстановки. Предположим, что, где константы и пока неизвестны, и попытаемся доказать это по индукции. При n=1 это верно, если взять достаточно большие, а и b. При n>1 имеем

Ниже мы покажем, что первую сумму можно оценить так:

Используя это, получим

Если выбрать, а так, чтобы аn/4 было больше. Следовательно, среднее время работы есть .

Доказательство оценки для суммы.

Нам осталось доказать оценку (3). Поскольку каждое слагаемое не превышает nlgn, получаем оценку

.

Для наших целей она не подходит — нам необходимо более точная оценка .

Если, заменив лишь на, мы, оставив k в неприкосновенности, получим оценку

.

Осталось лишь заметить, что заменяя на, мы прибавили, по крайней мере по k к каждому слагаемом первой половины суммы (где kn/2), всего примерно .

Более подробно,

.

При имеем. Поэтому

При n2. Оценка (3) доказана.