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

Размещено на http://www.allbest.ru/

Министерство Образования и Науки РФ ГОУ ВПО

«Дагестанский Государственный Технический Университет»

Филиал в г.Дербент

Курсовая работа

по дисциплине: «Структуры и алгоритмы обработки данных»

на тему:

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

Выполнил:

Студент 2 курса

Факультета ПОВТ и АС

Группы Д051

Проверил:

Ст. преподаватель

Дербент 2012 г.

Аннотация

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

Содержание

Введение

Быстрая сортировка (сортировка разделением)

Сортировка методом Шелла

Пирамидальная сортировка

Заключение

Приложение 1 (Реализация алгоритма быстрой сортировки на языке программирования Turbo Pascal)

Приложение 2 (Реализация алгоритма пирамидальной сортировки на языке программирования Turbo Pascal)

Список использованной литературы

Введение

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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

· Время -- основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение -- это и плохое поведение -- это . Идеальное поведение для упорядочения -- . Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью , использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за операций . При этом число n должно быть заранее известно;

· Память -- ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет) . Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

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

· Внешняя сортировка оперирует запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

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

o Объём данных не позволяет им разместиться в ОЗУ.

Быстрая сортировка (сортировка разделением)

Метод сортировки разделением был предложен Чарльзом Хоаром в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Быстрая сортировка является блестящим примером систематического применения принципов разделяй и властвуй и балансировка к сортировке обменами.

На первом этапе быстрой сортировки упорядочиваемый массив реорганизуется. Для этого в массиве выбирается главный элемент a[p]. Затем все элементы с ключами, меньшими a[p].key, размещаются слева от главного элемента, а элементы с ключами, большими либо равными a[p].key, размещаются справа от него.

Затем для полной сортировки массива достаточно (второй этап):

а) больше не трогать главный элемент, который находится на своем месте;

б) рекурсивно отсортировать подмассив A[1,p-1];

в) рекурсивно отсортировать подмассив A[p+1,n].

Реализуя второй этап, на практике обычно не устанавливают на свое место главный элемент, а просто включают его в один из подмассивов, например:

а) рекурсивно отсортировать подмассив A[1,p];

б) рекурсивно отсортировать подмассив A[p+1,n].

Выбор главного элемента

Это очень важный момент в алгоритме быстрой сортировки. Именно неудачный выбор на каждом шаге главного элемента обуславливает плохой показатель максимальной сложности. Пусть на некотором шаге на вход процедуры быстрой сортировки QuickSort поступили элементы массива с индексами от first до last. Тогда лучший способ выбрать главный элемент заключается в использованиигенератора случайных чисел для порождения целого числа p, first<=p<=last. Это число и определяет индекс главного элемента.

Реорганизация массива относительно главного элемента

Двигаясь от элемента с индексом first вправо, находят элемент с индексом f, ключ которого не меньше ключа главного элемента. Двигаясь от элемента с индексом last влево, находят элемент с индексом l, ключ которого не больше ключа главного элемента. Если оказалось, что элемент с индексом f расположен левее элемента с индексом l, то их меняют местами. Дальше движение влево продолжают с позиции f+1, движение вправо - с позиции l-1 до тех пор, пока не произойдет встреча.

Пример. Произвести разбивку массива 26, 49, 34, 1, 12, 37, 1, 38, 23 на два подмассива, приняв в качестве главного элемента a=23.

Решение.

Шаг 1. f=1, a[f]=26, l=9, a[l]=23; новый массив: 23, 49, 34, 1, 12, 37, 1, 38, 26.

Шаг 2. f=2, a[f]=49, l=7, a[l]=1; новый массив: 23, 1, 34, 1, 12, 37, 49, 38, 26.

Шаг 3. f=3, a[f]=34, l=5, a[l]=12; новый массив: 23, 1, 12, 1, 34, 37, 49, 38, 26.

Шаг 4. f=5, l=4; так как f>l, процесс завершен. Первый подмассив с индексами 1..l: 23, 1, 12, 1. Второй подмассив с индексами f..n: 34, 37, 49, 38, 26.

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

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

if last-first>порог then быстрая сортировка(...) else сортировка включением(...);.

Значение порога определяется характеристиками конкретной ЭВМ.

Быстрая сортировка рекомендуется для упорядочения последовательностей с размерностью от 100 и более элементов.

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

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

§ Лучший случай. Для этого алгоритма самый лучший случай -- если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.

§ Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.

§ На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N -- это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.

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

§ Худший случай даёт O(nІ) обменов. Но количество обменов и, соответственно, время работы -- это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Рассмотрим достоинства и недостатки быстрой сортировки.

Достоинства:

§ Самый быстродействующий (на практике) из всех существующих алгоритмов обменной сортировки -- быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных.

§ Простая реализация.

§ Хорошо сочетается с алгоритмами кэширования и подкачки памяти.

§ Хорошо работает на «почти отсортированных» данных -- если исходный массив уже близок к отсортированному, алгоритм не приводит к излишним перестановкам уже стоящих в правильном порядке элементов.

§ Существует очень эффективная разновидность (алгоритм Седжвика) для сортировки строк -- сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.

Недостатки:

§ Сильно деградирует как по скорости (до O(nІ)), так и по потреблению памяти, при неудачном выборе опорного элемента, который неизбежно случится при неудачных входных данных.

§ Примитивные реализации легко приводят к ошибке переполнения стека, особенно в средах, где размер стека сильно ограничен (ядра ОС). Развитые же реализации требуют постоянного выделения все новых и новых небольших блоков памяти, что не оптимально.

§ Неустойчив -- если требуется устойчивость, приходится расширять ключ.

Сортировка методом Шелла

алгоритм быстрая сортировка

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы

Чтобы понять, как работает метод Шелла, необходимо разобраться в механизме работы метода вставки

Сортировка включением состоит в следующем: выбирается некоторый элемент, сортируются другие элементы, после чего выбранный элемент “включается”, т.е. устанавливается на свое место среди других элементов. Рассмотрим подробнее соответствующий алгоритм.

...

for i:=2 to n do

begin

buf:=a[i]; y:=a[i].key; j:=i-1;

while (j>0) and (a[j].key>y) do begin a[j+]:=a[j]; j:=j-1 end

a[j+1]:=buf;

end

...

Таблица 3.1 иллюстрирует работу сортировки включением.

Таблица 3.1.

Начальные данные		i=3 (ситуация не изменилась: элемент с кл. 44 уже стоит на своем месте относительно элементов с кл. 22 и 33)
j	1	2	3	4		j	1	2	3	4
a[j].key	33	22	44	11		a[j].key	22	33	44	11
i=2 (элемент с кл. 22 встал на свое место относительно элемента с кл. 33)		i=4 (элемент с кл. 11 встал на свое место относительно элементов с кл. 22, 33, 44)
j	1	2	3	4		j	1	2	3	4
a[j].key	22	33	44	11		a[j].key	11	22	33	44

У этого алгоритма есть одно важное достоинство: в противоположность другим методам он имеет наилучшую эффективность, если в начальном массиве уже установлен некоторый порядок.

Пример. Если элемент с ключом 44 уже стоял на своем месте относительно элементов с ключами 22 и 33 (см. табл. 3.1), то на третьем шаге его не понадобилось передвигать.

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

Пример. Чтобы поставить элемент с ключом 11 на свое место (см. табл. 3.1), на четвертом шаге пришлось передвинуть элементы с ключами 22, 33, 44.

Усовершенствованная сортировка включением известна как сортировка Шелла. В 1959 году Д.Л.Шелл предложил вместо систематического включения элемента с индексом i в подмассив предшествующих ему элементов (этот способ противоречит принципу “балансировки”, почему и не позволяет получить эффективный алгоритм) включать этот элемент в подсписок, содержащий элементы с индексами i-h, i-2h, i-3h и т.д., где h - некоторая натуральная постоянная. Таким образом формируется массив, в котором h-серии элементов, отстоящих друг от друга на расстояние h, сортируются отдельно:

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

Для достаточно больших массивов результаты тестов показывают, что рекомендуемой можно считать последовательность таких hi, что hi+1=3 hi +1: ..., 364, 121, 40, 13, 4, 1. Начать процесс следует с такого элемента этой последовательности, который является ближайшим к целой части числа (n/9), превосходящим это число.

Пример. Если сортируется последовательность из n=1000 элементов, то целая часть числа (n/9) составит 111, значит h следует выбрать равным 121.

Ниже представлена процедура, реализующая метод Шелла.

Procedure ShellSort;

var h,j,k,y,kh:integer; buf:node;

begin

h:=1; while h<(n div 9) do h:=3*h+1;

while h>0 do

begin

for k:=1 to h do

begin

kh:=k+h;

while (kh<=n) do

begin

buf:=a[kh]; y:=buf.key; j:=kh-h;

while (j>=1) and (y<a[j].key) do begin a[j+h]:=a[j]; j:=j-h end;

a[j+h]:=buf; kh:=kh+h;

end

end;

h:=h div 3;

end

end; {* Shell*}

Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n^1.25), для худшего случая оценкой является O(n^1.5). Также следует сказать, что дополнительной памяти данный алгоритм не требует, но и не гарантирует сохранение порядка элементов с одинаковыми значениями.

Доказано, что максимальная сложность алгоритма Шелла составляет O(n5/4).

Доказано,что максимальная сложность алгоритма Шелла составляет O(n5/4). Так как



то этот вид сортировки пригоден для последовательностей, имеющих примерно до 70 тыс. элементов.

Пирамидальная сортировка

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

Пирамида определяется как некоторая последовательность ключей

K[L], …, K[R],

такая, что

K[i] K[2i] K[i] K[2i+1], (12.1)

для всякого i = L, …, R/2. Если имеется массив K[1], K[2], …, K[R], который индексируется от 1, то этот массив можно представить в виде двоичного дерева. Пример такого представления при R=10 показан на рисунке 12.4.



Рисунок 12.4 Массив ключей, представленный в виде двоичного дерева

Дерево, изображенное на рисунке 12.4, представляет собой пирамиду, поскольку для каждого i = 1, 2, …, R/2 выполняется условие (12.1). Очевидно, последовательность элементов с индексами i = R/2+1, R/2+2, …, R (листьев двоичного дерева), является пирамидой, поскольку для этих индексов в пирамиде нет сыновей.

Способ построения пирамиды «на том же месте» был предложен Р. Флойдом. В нем используется процедура просеивания, которую рассмотрим на следующем примере.

Предположим, что дана пирамида с элементами K[3], K[4], …, K[10] нужно добавить новый элемент K[2] для того, чтобы сформировать расширенную пирамиду K[2], K[3], K[4], …, K[10]. Возьмем, например, исходную пирамиду K[3], …, K[10], показанную на рисунке 12.5, и расширим эту пирамиду «влево», добавив элемент K[2]=44.

Рисунок 12.5 Пирамида, в которую добавляется ключ K[2]=44

Добавляемый ключ K[2] просеивается в пирамиду: его значение сравнивается с ключами узлов-сыновей, т. е. со значениями 15 и 28. Если бы оба ключа-сына были больше, чем просеиваемый ключ, то последний остался бы на месте, и просеивание было бы завершено. В нашем случае оба ключа_сына меньше, чем 44, следовательно, вставляемый ключ меняется местами с наименьшим ключом в этой паре, т. е. с ключом 15. Ключ 44 записывается в элемент K[4], а ключ 15 в элемент K[2]. Просеивание продолжается, поскольку ключи-сыновья нового элемента K[4] оказываются меньше его, происходит обмен ключей 44 и 18. В результате получаем новую пирамиду, показанную на рисунке 12.6.

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

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

Рисунок 12.6 Просеивание ключа 44 в пирамиду

Число итерация в процедуре просеивания не превосходит высоты пирамиды. Высота полного бинарного дерева из N узлов (пирамида является полным бинарным деревом), равна log2(N). Оба этапа сортировки реализуются циклами с количеством итераций, не превосходящими N, поэтому итоговая сложность пирамидальной сортировки - O(NlogN), причем эта оценка достигается даже в худшем случае.

Рассмотрим достоинства и недостатки пирамидальной сортировки.

Достоинства:

· Имеет доказанную оценку худшего случая O.

· Требует всего O дополнительной памяти.

Недостатки:

· Сложен в реализации.

· Неустойчив -- для обеспечения устойчивости нужно расширять ключ.

· На почти отсортированных массивах работает столь же долго, как и на хаотических данных.

· На одном шаге выборку приходится делать хаотично по всей длине массива -- поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.

Заключение

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

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. -- 2-е изд. -- М.: «Вильямс», 2007. -- С. 824. -- ISBN 5-8459-0082-4.

2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. -- 2-е изд. -- М.: «Вильямс», 2006. -- С. 1296. -- ISBN 5-8459-0857-4;

3. http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:saod:list_of_questions

Приложение 1

Реализация алгоритма быстрой сортировки на языке программирования Turbo Pascal

Program QSort; { быстрая сортировка Хоара }

Uses Crt;

Const M=100;

Type index=0..m;

Var

A: array [1..M] of integer;

K, R, N: index;

I, J, L, X, W: integer;

B: boolean;

Procedure Vvod(var N: index);

{ N-фактическое число элементов }

Begin

B:=True; N:=0;

While B do

begin

Write('Введите ключ (-1 - конец): ');

ReadLn(L);

if L>=0 then

begin

N:=N+1;

A[N]:=L

end

else B:=False

end;

End;

Procedure Vivod;

Begin

WriteLn;

For I:=1 to N do

Write(' ', A[I])

End;

Procedure Sort(K, R: index);

Begin

I:=K; { нижний индекс }

J:=R; { верхний индекс }

X:=A[(K+R) div 2];

Repeat

While A[I]<X do I:=I+1;

While A[J]>X do J:=J-1;

if I<=J then { A[I]>=X>=A[J] }

begin

W:=A[I]; A[I]:=A[J]; A[J]:=W;

I:=I+1; J:=J-1 { стало A[I-1]<=X<=A[J+1] }

end

Until I>J;

{ A[L]<=X для L=K,K+1,...,J }

{ A[L]>=X для L=I,...,R }

if K<J then Sort(K, J);

if I<R then Sort(I, R)

End;

Begin

ClrScr;

Vvod(n);

Sort(1, N);

Vivod;

ReadLn

End.

Приложение 2

Реализация алгоритма пирамидальной сортировки на языке программирования Turbo Pascal

Program Piramida; { пирамидальная сортировка }

Uses Crt;

Const M=100; { например }

Type Index=0..m;

Var

A: array [1..M] of integer;

L, R, N: index;

I, J, K, X: integer;

B: boolean;

Procedure Vvod(var n: Index);

{ N-фактическое число элементов }

Begin

B:=True; N:=0;

While B do

begin

Write('Введите ключ (-1 - конец): ');

ReadLn(L);

if L>=0 then

begin

N:=N+1;

A[N]:=L;

end

else B:=False

end;

End;

Procedure Vivod;

Begin

WriteLn;

For I:=1 to N do

Write(' ', A[I])

End;

Procedure Proseiv;

{ просеивание элемента A[K] в пирамиде A[K+1], A[K+2], …, A[R] }

Begin

B:=True; I:=K; J:=2*K; X:=A[K];

While (J<=R) and B do

begin

if J<R then { иначе один преемник у A[K] }

if A[J]>A[J+1] then J:=J+1;

if X>A[J] then

begin { спуск на уровень }

A[I]:=A[J]; I:=J; J:=2*J

end

else B:=False

{ в 2 последних операторах IF знаки сравнения '<', }

{ если в корень пирамиды посылается MAX значение }

end;

A[I]:=X;

End;

Begin { основная программа }

ClrScr;

Vvod(N);

K:=(N div 2)+1; R:=N;

While K>1 do

begin

K:=K-1;

Proseiv

end;

{ далее сортировка пирамиды на месте }

{ сейчас K=1 }

While R>1 do

begin

X:=A[1]; A[1]:=A[R]; A[R]:=X; R:=R-1;

Proseiv

end;

Vivod;

ReadLn

End.

Размещено на Allbest.ru