МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙФЕДЕРАЦИИ
КУРСОВАЯ РАБОТА
по дисциплине «Алгоритмическоеобеспечение ЭВС»
на тему «Методы внутреннейсортировки. />Обменная сортировка.
Сравнение с другими методамисортировки»
2010 г.
Содержание
Введение
1. Сортировкавключением
2. СортировкаШелла
3. Обменнаясортировка
4. Сортировкавыбором
5. Сортировкаразделением
6. Сравнениеметодов
Заключение
Приложение
Литература
Введение
Целью даннойкурсовой работы является изучения основных алгоритмов внутренней сортировкимассивов данных, сравнение сложности их реализации и производительности. Болееподробно рассмотрен метод обменной сортировки.
Если обратиться к литературе, то можно обнаружить два крайнихподхода к представлению материала. Некоторые авторы любят излагать материал навысоком теоретическом уровне. Например, для того, чтобы ввести понятие типаданных и предложить классификацию возможных типов, используются развитыемеханизмы абстрактной алгебры; при описании алгоритмов в обязательном порядкеприводятся асимптотические оценки их сложности. Другой подход состоит вмаксимальном приближении к практике. Обычно выбирается некоторый конкретныйязык программирования, и все описываемые структуры данных и алгоритмыпредставляются на этом языке.
/>1. Сортировка включением
Одним из наиболее простых и естественных методов внутреннейсортировки является сортировка с простыми включениями. Идея алгоритма оченьпроста. Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элементамассива, начиная со второго, производится сравнение с элементами с меньшиминдексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2]...) и до тех пор, пока для очередного элемента a[j] выполняется соотношениеa[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такойэлемент a[j], что a[j]
Легко видеть, что в лучшем случае (когда массив ужеупорядочен) для выполнения алгоритма с массивом из n элементов потребуется n-1сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратномпорядке) потребуется n?(n-1)/2 сравнений и столько же пересылок. Таким образом,можно оценивать сложность метода простых включений как O(n2).
Можно сократить число сравнений, применяемых в методе простыхвключений, если воспользоваться тем фактом, что при обработке элемента a[i]массива элементы a[1], a[2], ..., a[i-1] уже упорядочены, и воспользоваться дляпоиска элемента, с которым должна быть произведена перестановка, методомдвоичного деления. В этом случае оценка числа требуемых сравнений становитсяO(n?log n). Заметим, что поскольку при выполнении перестановки требуетсясдвижка на один элемент нескольких элементов, то оценка числа пересылокостается O(n2).
Таблица 1.1 Пример сортировки методом простого включенияНачальное состояние массива 8 23 5 65 44 33 1 6 Шаг 1 8 23 5 65 44 33 1 6 Шаг 2
8 5 23 65 44 33 1 6
5 8 23 65 44 33 1 6 Шаг 3 5 8 23 65 44 33 1 6 Шаг 4 5 8 23 44 65 33 1 6 Шаг 5
5 8 23 44 33 65 1 6
5 8 23 33 44 65 1 6 Шаг 6
5 8 23 33 44 1 65 6
5 8 23 33 1 44 65 6
5 8 23 1 33 44 65 6
5 8 1 23 33 44 65 6
5 1 8 23 33 44 65 6
1 5 8 23 33 44 65 6 Шаг 7
1 5 8 23 33 44 6 65
1 5 8 23 33 6 44 65
1 5 8 23 6 33 44 65
1 5 8 6 23 33 44 65
1 5 6 8 23 33 44 65
2.Сортировка Шелла
Дальнейшим развитием метода сортировки с включениями являетсясортировка методом Шелла, называемая по-другому сортировкой включениями суменьшающимся расстоянием. Мы не будем описывать алгоритм в общем виде, аограничимся случаем, когда число элементов в сортируемом массиве являетсястепенью числа 2. Для массива с 2n элементами алгоритм работает следующимобразом. На первой фазе производится сортировка включением всех пар элементовмассива, расстояние между которыми есть 2(n-1). На второй фазе производитсясортировка включением элементов полученного массива, расстояние между которымиесть 2(n-2). И так далее, пока мы не дойдем до фазы с расстоянием междуэлементами, равным единице, и не выполним завершающую сортировку с включениями.Применение метода Шелла к массиву, используемому в наших примерах, показано втаблице 2.2.
Таблица1.2.Пример сортировки методом ШеллНачальное состояние массива 8 23 5 65 44 33 1 6 Фаза 1 (сортируются элементы, расстояние между которыми четыре)
8 23 5 65 44 33 1 6
8 23 5 65 44 33 1 6
8 23 1 65 44 33 5 6
8 23 1 6 44 33 5 65 Фаза 2 (сортируются элементы, расстояние между которыми два)
1 23 8 6 44 33 5 65
1 23 8 6 44 33 5 65
1 23 8 6 5 33 44 65
1 23 5 6 8 33 44 65
1 6 5 23 8 33 44 65
1 6 5 23 8 33 44 65
1 6 5 23 8 33 44 65 Фаза 3 (сортируются элементы, расстояние между которыми один)
1 6 5 23 8 33 44 65
1 5 6 23 8 33 44 65
1 5 6 23 8 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
В общем случае алгоритм Шелла естественно переформулируетсядля заданной последовательности из t расстояний между элементами h1, h2, ...,ht, для которых выполняются условия h1 = 1 и h(i+1) 3. Обменная сортировка
Простая обменная сортировка (в просторечии называемая«методом пузырька») для массива a[1], a[2], ..., a[n] работаетследующим образом. Начиная с конца массива сравниваются два соседних элемента(a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значенияэлементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д.,пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого наместе a[1] окажется элемент массива с наименьшим значением. На втором шагепроцесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. Напоследнем шаге будут сравниваться только текущие значения a[n] и a[n-1].Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые«легкие») постепенно «всплывают» к верхней границе массива.Пример сортировки методом пузырька показан в таблице 2.3.
Таблица 1.3.Пример сортировки методом ПузырькаНачальное состояние массива 8 23 5 65 44 33 1 6 Шаг 1
8 23 5 65 44 33 1 6
8 23 5 65 44 1 33 6
8 23 5 65 1 44 33 6
8 23 5 1 65 44 33 6
8 23 1 5 65 44 33 6
8 1 23 5 65 44 33 6
1 8 23 5 65 44 33 6 Шаг 2
1 8 23 5 65 44 6 33
1 8 23 5 65 6 44 33
1 8 23 5 6 65 44 33
1 8 23 5 6 65 44 33
1 8 5 23 6 65 44 33
1 5 8 23 6 65 44 33 Шаг 3
1 5 8 23 6 65 33 44
1 5 8 23 6 33 65 44
1 5 8 23 6 33 65 44
1 5 8 6 23 33 65 44
1 5 6 8 23 33 65 44 Шаг 4
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65 Шаг 5
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65 Шаг 6
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65 Шаг 7 1 5 6 8 23 33 44 65
Для метода простой обменной сортировки требуется числосравнений nx(n-1)/2, минимальное число пересылок 0, а среднее имаксимальное число пересылок — O(n2).
Метод пузырька допускает три простых усовершенствования.Во-первых, как показывает таблица 3, на четырех последних шагах расположениезначений элементов не менялось, (массив оказался уже упорядоченным). Поэтому,если на некотором шаге не было произведено ни одного обмена, то выполнениеалгоритма можно прекращать. Во-вторых, можно запоминать наименьшее значениеиндекса массива, для которого на текущем шаге выполнялись перестановки.Очевидно, что верхняя часть массива до элемента с этим индексом ужеотсортирована, и на следующем шаге можно прекращать сравнения значений соседнихэлементов при достижении такого значения индекса. В-третьих, метод пузырькаработает неравноправно для «легких» и «тяжелых» значений.Легкое значение попадает на нужное место за один шаг, а тяжелое на каждом шагеопускается по направлению к нужному месту на одну позицию.
На этих наблюдениях основан метод шейкерной сортировки(ShakerSort). При его применении на каждом следующем шаге меняется направлениепоследовательного просмотра. В результате на одном шаге «всплывает»очередной наиболее легкий элемент, а на другом «тонет» очереднойсамый тяжелый. Пример шейкерной сортировки приведен в таблице 2.4.
Таблица 4. Пример шейкерной сортировкиНачальное состояние массива 8 23 5 65 44 33 1 6 Шаг 1
8 23 5 65 44 33 1 6
8 23 5 65 44 1 33 6
8 23 5 65 1 44 33 6
8 23 5 1 65 44 33 6
8 23 1 5 65 44 33 6
8 1 23 5 65 44 33 6
1 8 23 5 65 44 33 6 Шаг 2
1 8 23 5 65 44 33 6
1 8 5 23 65 44 33 6
1 8 5 23 65 44 33 6
1 8 5 23 44 65 33 6
1 8 5 23 44 33 65 6
1 8 5 23 44 33 6 65 Шаг 3
1 8 5 23 44 6 33 65
1 8 5 23 6 44 33 65
1 8 5 6 23 44 33 65
1 8 5 6 23 44 33 65
1 5 8 6 23 44 33 65 Шаг 4
1 5 6 8 23 44 33 65
1 5 6 8 23 44 33 65
1 5 6 8 23 44 33 65
1 5 6 8 23 33 44 65 Шаг 5
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65
Шейкерная сортировка позволяет сократить число сравнений (пооценке Кнута средним числом сравнений является (n2 — n?(const + ln n)), хотяпорядком оценки по-прежнему остается n2. Число же пересылок, вообще говоря, неменяется. Шейкерную сортировку рекомендуется использовать в тех случаях, когдаизвестно, что массив «почти упорядочен»./>
4. Сортировка выбором
При сортировке массива a[1], a[2], ..., a[n] методом простоговыбора среди всех элементов находится элемент с наименьшим значением a[i], иa[1] и a[i] обмениваются значениями. Затем этот процесс повторяется дляполучаемых подмассивов a[2], a[3], ..., a[n],… a[j], a[j+1], ..., a[n] дотех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моментунаибольшее значение. Работа алгоритма иллюстрируется примером в таблице 2.5.
Таблица 5. Пример сортировки простым выборомНачальное состояние массива 8 23 5 65 44 33 1 6 Шаг 1 1 23 5 65 44 33 8 6 Шаг 2 1 5 23 65 44 33 8 6 Шаг 3 1 5 6 65 44 33 8 23 Шаг 4 1 5 6 8 44 33 65 23 Шаг 5 1 5 6 8 33 44 65 23 Шаг 6 1 5 6 8 23 44 65 33 Шаг 7 1 5 6 8 23 33 65 44 Шаг 8 1 5 6 8 23 33 44 65
Для метода сортировки простым выбором требуемое числосравнений — nx(n-1)/2. Порядок требуемого числа пересылок (включаяте, которые требуются для выбора минимального элемента) в худшем случаесоставляет O(n2). Однако порядок среднего числа пересылок есть O(n?ln n), что вряде случаев делает этот метод предпочтительным./>
5. Сортировка разделением (Quicksort)
Метод сортировки разделением был предложен Чарльзом Хоаром(он любит называть себя Тони) в 1962 г. Этот метод является развитием методапростого обмена и настолько эффективен, что его стали называть «методомбыстрой сортировки — Quicksort».
Основная идея алгоритма состоит в том, что случайным образомвыбирается некоторый элемент массива x, после чего массив просматриваетсяслева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массивпросматривается справа, пока не встретится элемент a[j] такой, что a[j]
Таблица 6. Пример быстрой сортировкиНачальное состояние массива 8 23 5 65 |44| 33 1 6 Шаг 1 (в качестве x выбирается a[5])
|--------|
8 23 5 6 44 33 1 65
|---|
8 23 5 6 1 33 44 65 Шаг 2 (в подмассиве a[1], a[5] в качестве x выбирается a[3])
8 23 |5| 6 1 33 44 65
|--------|
1 23 5 6 8 33 44 65
|--|
1 5 23 6 8 33 44 65 Шаг 3 (в подмассиве a[3], a[5] в качестве x выбирается a[4])
1 5 23 |6| 8 33 44 65
|----|
1 5 8 6 23 33 44 65 Шаг 4 (в подмассиве a[3], a[4] выбирается a[4])
1 5 8 |6| 23 33 44 65
|--|
1 5 6 8 23 33 44 65
Алгоритм недаром называется быстрой сортировкой, посколькудля него оценкой числа сравнений и обменов является O(n?log n). На самом деле,в большинстве утилит, выполняющих сортировку массивов, используется именно этоталгоритм./>
6. Сравнение методов
Для сравнения методов сортировки была написана программа, позволяющаявыполнить сортировку пятью способами, по возрастанию или убыванию. Заполнениемассива производится случайными данными.
/>
Рис 1. Интерфейс программы.
После выполнения сортировки программа выводит количествосравнений и перестановок. При сравнении заполнялась таблица зависимости числаперестановок и числа сравнений от размера массива.
Таблица 7Метод Сравнений Перестановок Кол-во 16 32 64 128 256 16 32 64 128 256 Пузырёк 135 527 2079 8255 32895 69 201 1150 3644 14648 QuickSort
70 223 486
1228
2771 20 70 160 399 887 Выбором 120 496 2016 8128 32640
11
29
58
124
249 Шелла 73
186
484 1348 3771 19 54 200 756 2537 Вставками 74 315 1177 4819 17525 46 257 1056 4566 17018
На основании данных таблицы были построены графики.
/>
Рис 2. Зависимость числа перестановок от размера массива
/>
Рис 3. Зависимость числа сравнений от размера массива.
Выводы
По результатам замеров производительности методов можносделать следующие выводы:
1. Наиболееуниверсальным методом, является метод быстрой сортировки («QuickSort»), он показывает стабильно высокиерезультаты на любых размерах массивов. На втором месте находится метод Шелла.Его использование может быть обосновано большее простым алгоритмом с точкизрения программиста.
2. Метод вставкиэффективен, при условии большого времени выполнения операций перестановки, таккак он является абсолютным лидером по количеству перестановок, проигрывая приэтом по количеству сравнений.
3. При использованиинебольших массивов данных нет большой разницы по скорости между методамисортировки, поэтому целесообразнее применять метод Пузырька или метод вставок.
4. Исследованиепроводилось на массивах с большой степенью неупорядоченности. Для массивов,которые уже являются почти отсортированными, наиболее применим метод сортировкивставками.
Приложение
Блок схемы.
Обменная сортировка.
/>
Сортировка выбором.
/>
Сортировка вставкой.
/>