Рассмотрим алгоритмы сортировки «на месте», то есть те алгоритмы в которых не используется копирование массива.

Удобной мерой эффективности алгоритмов сортировки «на месте» является число необходимых сравнений в ходе сортировки и число необходимых пересылок элементов.

Эффективные алгоритмы сортировки требуют порядка

сравнений, где N - число элементов, а С - число необходимых сравнений.

Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка

Методы сортировки «на месте» можно разбить на три основных класса:

1. сортировка выбором

2. сортировка вставками

3. сортировка обменом

В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется местами предпоследним элементом и т.д. (рисунок 1).

Рисунок 1. Сортировка простым выбором

В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части (рисунок 2).

Рисунок 2. Сортировка простыми включениями

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

Рисунок 3. Сортировка простым обменом

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

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

Рассмотрим подробнее основные типы и виды сортировок (сначала простые сортировки затем более сложные).

1.1 Сортировка массива простым выбором

Метод основан на следующем правиле:

1. Выбирается элемент с наибольшим значением ключа

2. Он меняется местами с последним элементом arr [s-1]. Затем эти операции повторяются с оставшимися первыми s-1 элементами, затем - с s-2 первыми элементами и т.д. до тех пор, пока не останется только первый элемент - наименьший. Пример сортировки методом простого выбора показан на рисунке 4:

Рисунок 4. Сортировка массива простым выбором

Эффективность сортировки простым выбором. Число сравнений ключей не зависит от начального порядка ключей. Операция сравнения выполняется в теле цикла с управляющей переменной k и средним числом повторений size/2. Этот цикл, в свою очередь, находится в теле цикла с управляющей переменной L и числом повторений size ?1. Таким образом, число сравнений

С=(size ?1)* size ?1/2

Число пересылок, напротив, зависит от начального порядка ключей. Если принять, что операция сравнения в теле цикла по k дает результат «истина» в половине случаев, то среднее число пересылок в этом цикле равно size/4. Цикл по L, как указывалось выше, выполняется size ?1 раз и в теле цикла выполняется три пересылки и цикл по k. С учетом этого число пересылок:

М=(3+ size/4)*(size ?1)

Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально .

1.2 Сортировка массива простыми включениями

Mmax = (n2+3n-4)/2.

Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],…, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.

1.3 Сортировка массива простым обменом («метод пузырька»)

Очевидно, что в наихудшем случае, когда минимальное значение ключа элемента имеется у самого правого элемента, число просмотров равно size ?1.

Эффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное ? size -1, а среднее ? size/2. Следовательно,

12 44 18 55

12 42 44 18 06 55 67 94

18 44

06 44

12 42 18 06 44 55 67 94

18 42

06 42

12 18 06 42 44 55 67 94

06 18

12 06 18 42 44 55 67 94

06 12

06 12 18 42 44 55 67 94

Рисунок 6. Пример сортировки массива простым обменом

1.4 Сортировка массива сложным выбором (с помощью двоичного дерева)

Метод сортировки основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов n-2 сравнений. Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец при помощи всего n-1 сравнений мы можем построить дерево, как показано на рис. 1, выбора и определит корень, как наименьший ключ. На втором шаге мы спускаемся по пути, указанном наименьшим ключом, и исключаем его, последовательно заменяя либо на «дыру» (или ключ бесконечность), либо на элемент, находящийся на противоположной ветви промежуточного узла Элемент оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся и может быть исключен. После n таких шагов дерево становится пустым (т.е. состоит из «дыр»), и процесс сортировки закончен.

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

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

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

Пирамида определяется как последовательность ключей hl, hl+1,…, hr, такая, что hi <= h2i, hi <= h2i+1 для всякого i =l,…, r/2. Если двоичное дерево представлено в виде массива, как показано на рис. 1, то, следовательно, деревья сортировки на рис. 2 и 3 являются пирамидами, и, в частности, элемент h1 пирамиды является ее наименьшим элементом h1 = min (h1…hn).

Теперь предположим, что дана пирамида с элементами hl+1,…, hr для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду hl,…, hr. Возьмем, например, исходную пирамиду h1,…, h7, показанную на рис. 2, и расширим эту пирамиду «влево», добавив элемент h1=44. Новый элемент x сначала помещается в вершину дерева, а затем «просеивается» по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом формируется новая пирамида. На рисунке 8 продемонстрирована пирамидальная сортировка.

Рисунок 8. Процесс построения дерева

В данном примере значение 44 сначала меняется местами с 06, затем 12, и так формируется дерево. Далее процесс просеивания будем формулировать следующим образом: i, j - пара индексов, обозначающих элементы, которые нужно менять местами на каждом шаге просеивания.

Для восьми элементов из нашего примера минимальное и максимальное количества пересылок дают следующие исходные последовательности:

Мmin = 13 для последовательности

94, 67, 44, 55, 12, 42, 18, 6

Mmax=24 для последовательности

18, 42, 12, 44, 6, 55, 67, 94

Среднее число пересылок равно приблизительно nlog(n)/2 и отклонения от этого значения сравнительно малы.

1.6 Сортировка Шелла

На рисунке 9 продемонстрирована сортировка методом Шелла:

Рисунок 9. Сортировка Шелла

На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В нашем примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2-сортировкой. Наконец на третьем проходе все элементы сортируются обычной 1-сортировкой включением.

На каждом шаге в сортировке участвует либо сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок. Очевидно, что этот метод дает упорядоченный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки. Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через

h1, h2,…, hn с условиями ht=1, hi+1 < hi.

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

1.7 Сложная сортировка обменом (сортировка Хоора)

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

Ожидаемое число обменов равно приблизительно n / 6. Быстрая сортировка все же имеет свои «подводные камни». Прежде всего, при небольших значениях n ее эффективность невелика, как и у всех усовершенствованных методов. Ее преимущество по сравнению с другими усовершенствованными методами заключается в том, что для сортировки уже разделенных небольших подмассивов легко можно применить какой-либо простой метод.

1.8 Общий анализ приведенных сортировок

Приведем выводы по простым методам сортировки:

1. Время сортировки пропорционально квадрату размерности массива

2. Более точные оценки производительности простых методов сортировки показывают, что наиболее быстрой является сортировка вставками, а наиболее медленной ? сортировка обменом.

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

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

Сравним простые и сложные методы сортировки по производительности:

Таблица 1. Сравнительные показатели производительности различных методов сортировки массивов

Из приведенных в таблице данных следует, в частности, для относительно небольшого массива в 512 элементов:

1) Худшая по производительности из простых сортировок (сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоора.

2) Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4.2 раза чем худшая по производительности из сложных сортировок (сортировка Шелла).

3) При увеличении размера массива указанные выше эффекты проявляются в большей степени

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

2.1 Разработка сценария отображения выбранной для представления информации

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

Данные для сортировки будут генерироваться программно, с помощью функции randomize.

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

Далее на экране перед ним будет выведен список заданных и список отсортированных элементов.

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

2.2 Разработка и функции быстрой обменной сортировки на основе алгоритма обмена данных

Для создания функций сортировки Хоара составим словесное описание алгоритма сортировки.

Алгоритм сортировки Хоара рассмотрен в разделе 1.7 курсового проекта. Для того, чтобы запрограммировать данный алгоритм сортировки представим его сначала в виде блок-схемы для более наглядного отображения его функционирования (см. приложение 2).

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

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

два индекса - l и j, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;

вычисляется опорный элемент r;

индекс l последовательно увеличивается до r или до тех пор, пока l-й элемент не превысит опорный;

индекс j последовательно уменьшается до r или до тех пор, пока j-й элемент не окажется меньше опорного;

если j = l - найдена середина массива - операция разделения закончена, оба индекса указывают на опорный элемент;

если l < j - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или j) дошла до опорного элемента, то при обмене значение r изменяется на j или l соответственно.

Рекурсивно упорядочиваем подмассивы, лежащие, слева и справа от опорного элемента.

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

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

На основе данной блок-схемы можно разработать функцию, выполняющую сортировку массива методом Хоара на языке программирования C++:

void QuickSort (int left, int right, a[]) // функция сортировки

{

int i, j, r; // объявление переменных

j=right, i=left; // приравниваем крайние элементы к индексам

r=a[(left+right)/2];

 // находим опорный элемент

while (i>j)

{

while (a[i]. <r) i++; // ищем элемент больше опорного

while (a[j]. >r) j-; // меньше опорного

{

temp=a[i];

a[i]=a[j]; // меняем элементы местами

a[j]=temp;

i++;

j -;

}

}

if (left<j) QuickSort (inf, left, j); // рекурсивно сортируем левую и

if (right>i) QuickSort (inf, i, right); правую части

2.3 Разработка и функции быстрой обменной сортировки на основе таблицы адресов

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

В этом случае функция сортировки будет иметь следующий вид.

void QuickSort (int left, int right, *a[]) // функция сортировки

{

int i, j, r; // объявление переменных

j=right, i=left; // приравниваем крайние элементы к индексам

r=a[(left+right)/2];

 // находим опорный элемент

while (i>j)

{

while (*a[i]. <r) i++; // ищем элемент больше опорного

while (*a[j]. >r) j-; // меньше опорного

{

temp=a[i];

a[i]=a[j]; // меняем элементы местами

a[j]=temp;

i++;

j -;

}

}

if (left<j) QuickSort (inf, left, j); // рекурсивно сортируем левую и

if (right>i) QuickSort (inf, i, right); правую части

2.4 Тестирование разработанных функций сортировок

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

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

struct MyStruct

{

int key;

double info;

};

Т.е. в ней имеется два поля, первое - key типа int, и второе - info (информационное поле) типа double.

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

В то же время, при использовании второй функции сортировки - QuickSort index, которая выполняет сравнение этих же элементов, но уже меняет местами при необходимости не сами блоки данных в памяти, а лишь указатели на эти блоки, занимающие вместо 12-и байт всего 4.

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

Теоретический анализ измерения времени сортировки

При разработке алгоритмов сортировок в данной программе также была предусмотрена возможность измерения времени сортировки в миллисекундах. Запуская программу на выполнение, пользователю предоставляется возможность задать количество сортируемых элементов, которые в последствии сгенерируются случайным образом в диапазоне от -50 до 50, и далее будет предоставлен выбор метода сортировки (перемещение данных в памяти или указателей на данные методом Быстрой обменной сортировки), после чего случайно сгенерированные элементы будут отсортированы и выведены на экран, а также будет показано время сортировки в миллисекундах.

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

3.2 Экспериментальное сравнение алгоритмов сортировок методом простых вставок и методом пузырька

По результатам измерений составлена таблица времени сортировок элементов массива структур двумя способами:

Таблица 1 - Результаты измерения времени сортировок

Построим по данным таблицы графики зависимости скорости сортировки от количества элементов - график 1

График 1 - Графики зависимостей времени сортировки от количества элементов

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

Заключение

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

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

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

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

Список литературы