Федеральное агентство по образованию Российской Федерации
Самарский государственный аэрокосмический университет
Филиал в г. Тольятти
Кафедра Радиоэлектроники и Системотехники
сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька
Пояснительная записка к курсовой работе
Руководитель
проекта Репина И.Г.
Исполнитель
студент гр.62048
Тольятти 2009
Реферат
Курсовая работа.
Пояснительная записка 34 с., 14 рис.,2 блок-схемы, 3 табл., 4 источника
АЛГОРИТМЫ, ПРОГРАММИРОВАНИЕ, С++, СОРТИРОВКА МЕТОДОМ ВСТАВОК, СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА, СРАВНЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ
Объектом исследования является алгоритмы сортировки.
Цель работы - описать, разработать и запрограммировать два алгоритма сортировки по указанному методу: первый алгоритм - сортировка методом простых вставок, второй - сортировка методом пузырька. Протестировать программу и выполнить экспериментальное сравнение разработанных алгоритмов сортировки, выявив зависимость среднего времени сортировки от числа сортируемых элементов. Построить графики.
В процессе работы были созданы две функции, осуществляющие сортировку любого количества элементов, первый - методом простых вставок, второй - на основе сортировки таблицы адресов.
Содержание
Введение
1. Анализ поставленной задачи и постановка задачи на проектирование
1.1 Поиск, анализ и выбор основных вопросов, подлежащих реализации
1.2 Выбор программного обеспечения по реализации ИТ
1.3 Обоснование требований к разрабатываемой ИТ
2. Обзор алгоритмов сортировки
2.1 Сортировка массива простыми включениями
2.2 Сортировка массива простым обменом ("метод пузырька")
2.3 Сортировка массива сложным выбором (с помощью двоичного дерева)
2.4 Пирамидальная сортировка
2.5 Сортировка Шелла
2.6 Сложная сортировка обменом (сортировка Хоора)
2.7 Общий анализ приведенных сортировок
2.8 Теоретическое сравнение сортировок методом простых вставок и методом пузырька
2.9 Разработка и программирование алгоритма сортировки методом простых вставок
3. Разработка и программирование алгоритма сортировки методом пузырька
4. Тестирование разработанных функций сортировки методом простых вставок и методом пузырька
5. Экспериментальное сравнение разработанных алгоритмов сортировки
Заключение
Список литературы
Приложение
Введение
На данный момент существует множество алгоритмов сортировки данных. Зачастую выбор алгоритма решения задачи зависит от структуры сортируемых данных. В случае сортировки эта зависимость имеет большое значение, и методы сортировки обычно разделяют на две категории:
Сортировка массивов (внутренняя сортировка)
Сортировка последовательных файлов (внешняя сортировка)
При внутренней сортировке массивы располагаются в оперативной памяти ЭВМ, что обеспечивает быстрый произвольный доступ к данным.
При внешней сортировке файлы хранятся в более "медленной", но более вместительной внешней памяти, т.е. на запоминающих устройствах с механическим передвижением (магнитных дисках и других носителях).
Критериями оценки методов сортировки являются:
количество операций сравнения пар ключей
число перестановок элементов
экономное использование памяти
Цель курсовой работы:
систематизация, углубление и активное применение знаний по программированию в среде С++
рассмотреть основные алгоритмы сортировки
разработать, протестировать и проанализировать алгоритмы сортировки методом простых вставок и методом пузырька
Оценить производительность данных алгоритмов и сравнить их между собой по различным характеристикам
Актуальность:
С помощью ЭВМ можно решать самые разные задачи, в том числе автоматически выполнять требуемую сортировку данных. Сортировка может требоваться в различных ситуациях, например когда нужно отобразить визуально распределение данных. Для различных данных существуют определенные методы сортировок повышающие производительность и скорость сортировки именно для этого типа данных.
Рассматриваемые в данной работе сортировки методы сортировки являются относительно простыми, и хотя их эффективность ниже чем у более сложных и совершенных методов, но они так же имеют ряд преимуществ, и к тому же лежат в основе большинства других методов сортировки.
Новизна:
Рассматриваемые методы сортировок в силу своей простоты особенно хорошо подходят для изучения свойств большинства принципов сортировки, программы, основанные на данных методах легки для понимания и коротки (это также позволяет экономить память, занимаемую программой). Так же важно отметить, что хотя сложные алгоритмы требуют меньшего числа операций, но эти операции являются более сложными. Поэтому при относительно малом количестве сортируемых элементов простые методы сортировки работают достаточно быстро.
1. Анализ поставленной задачи и постановка задачи на проектирование
1.1 Поиск, анализ и выбор основных вопросов, подлежащих реализации
В соответствии с целями данного курсового проекта, возможно начать проектирование и анализ требуемых для проекта программ.
В начале необходимо отметить основные типы и виды сортировок, их основные характеристики. Это необходимо для выделения основных отличий рассматриваемых в курсовом проекте сортировок от других существующих методов сортировок. По рекомендованной литературе выполнить теоретическое сравнение алгоритмов сортировок, рассматриваемых в рамках курсового проекта. Построить блок-схемы, наглядно отображающие принцип работы алгоритмов сортировок методом простых вставок и методом "пузырька".
Далее следует описать, разработать и запрограммировать алгоритмы сортировки методом перестановки данных рассматриваемые в курсовом проекте. Протестировать программы (массивы должны сортироваться) и отобразить это в отчете. Выполнить сравнительный анализ работы двух алгоритмов сортировки, и выявить зависимость среднего времени сортировки от числа сортируемых элементов, построить график, отображающий данную зависимость.
1.2 Выбор программного обеспечения по реализации ИТ
При написании программ для реализации сортировок массивов был использован язык программирования С++. Это один из широко используемых языков программирования, который можно использовать для написания программ, работающих в операционной среде Windows. Среда Borland C++ Builder 6- это сложный механизм, обеспечивающий высокоэффективную работу программиста
Интегрированная среда разработки C++ Builder представляет собой многооконную систему. Вид интегрированной среды разработки (интерфейс) может различаться в зависимости от настроек. Кроме стандартных окон, на экране могут присутствовать и другие окна, отображаемые при вызове соответствующих средств, например, Image Editor (Редактор изображений). Окна C++ Builder (но не главное) можно перемещать, убирать с экрана, а также изменять их размеры.
Несмотря на наличие многих окон, C++ Builder является одно-документной средой, т.е. позволяет одновременно работать только с одним приложением (проектом приложения). Название проекта приложения выводится в строке заголовка главного окна в верхней части экрана.
Если свернуть главное окно, то происходит минимизация всего интерфейса C++ Builder и, соответственно, всех открытых окон. При закрытии главного окна работа с C++ Builder прекращается.
Borland C++ Builder 6, вобрав в себя всё самое лучшее от предыдущих версий, предоставляет ряд новых возможностей. Так, например, стал более удобным и современным интерфейс среды программирования, создаваемые C++ Builder программы учитывают архитектуру современных процессоров, существенно расширены возможности отладчика.
Borland C++ Builder 6 может работать в среде операционных систем от Windows 95 до Windows XP. Особенных требований к компьютеру система не предъявляет, за исключением того, что процессор должен быть типа Pentium, оперативной памяти - не менее 32 Мбайт и достаточное количество свободной дисковой памяти.
1.3 Обоснование требований к разрабатываемой ИТ
Касательно выбора шрифтов и прочих средств представления курсового проекта - шрифт выбран размером 14 Times New Roman для удобства чтения представленной информации. Также в курсовом проекте используются таблицы и рисунки для более наглядного представления и объяснения информации, обозначенные соответствующими подписями и пояснениями.
Все рисунки, таблицы, схемы и другая возможная информация, встречающиеся в курсовом проекте, имеют явные указания и подписи по своему размещению, потому найти их не составляет никакого труда.
2. Обзор алгоритмов сортировки
Сортировка - это процесс перестановки объектов данного множества в определённом порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. Поэтому элементы сортировки присутствуют во многих задачах прикладного программирования.
Рассмотрим алгоритмы сортировки "на месте", то есть те алгоритмы в которых не используется копирование массива.
Удобной мерой эффективности алгоритмов сортировки "на месте" является число необходимых сравнений в ходе сортировки и число необходимых пересылок элементов.
Эффективные алгоритмы сортировки требуют порядка
сравнений, где N - число элементов, а С - число необходимых сравнений.
Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка
Методы сортировки "на месте" можно разбить на три основных класса:
сортировка выбором
сортировка вставками
сортировка обменом
В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется
местами предпоследним элементом и т.д. (рисунок 1).
Рисунок 1. Сортировка простым выбором
В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части (рисунок 2).
Рисунок 2. Сортировка простыми включениями
Основная характеристика сортировки обменом - перестановка местами двух соседних элементов, если они расположены не так, как требует отсортированный массив.
Рисунок 3. Сортировка простым обменом
В рассмотренной классификации существуют разные алгоритмы. Они отличаются сложностью, быстротой выполнения, последовательностью операций.
Например:
сортировка вставками;
пузырьковая сортировка;
корневая сортировка;
пирамидальная сортировка;
сортировка слиянием;
быстрая сортировка;
сортировка Шелла и др.
Рассмотрим подробнее основные типы и виды сортировок (сначала простые сортировки затем более сложные).
Сортировка массива простым выбором
Метод основан на следующем правиле:
Выбирается элемент с наибольшим значением ключа
Он меняется местами с последним элементом 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)
Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально .
2.1 Сортировка массива простыми включениями
Метод простых вставок предполагает разделение всего массива элементов на упорядоченную часть, которая вначале содержит лишь один элемент, и неупорядоченную. Очередной элемент из неупорядоченной части вставляется в определенное место упорядоченной части, проходя сравнение с ее элементами. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы "просеивать" выбранный элемент, сравнивая его с очередным элементом a [j] и либо вставляя, либо пересылая a [i] направо и продвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях: найден элемент a [j] с ключом меньшим, чем ключ x или достигнут левый конец готовой последовательности.
При этом упорядоченная часть удлиняется на один элемент. Сортировка заканчивается при окончании неупорядоченной части.
При данной сортировке общее число сравнений приблизительно равно
,
При этом требуется количество проходов по данным P
Рассмотрим пошагово сортировку методом простых вставок на рис.5
Рисунок 5. Пример сортировки массива простыми включениями
Число Ci сравнений ключей при i-м просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число Мi пересылок (присваиваний) равно Ci+2 (учитывая барьер). Поэтому общее число сравнений и пересылок есть
Cmin = n-1 Mmin = 2 (n-1)
Cср. = (n2+n-2) /4 Mср. = (n2+9n-10) /4
Cmax = ( (n2+n) - 1) /2 Mmax = (n2+3n-4) /2.
Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a [1],…, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.
2.2 Сортировка массива простым обменом ("метод пузырька")
Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Пример сортировки методом "пузырька" приведен на рисунке 6.
Очевидно, что в наихудшем случае, когда минимальное значение ключа элемента имеется у самого правого элемента, число просмотров равно size −1.
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. Пример сортировки массива простым обменом
Эффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное − size -1, а среднее − size/2.
Следовательно,
2.3 Сортировка массива сложным выбором (с помощью двоичного дерева)
Метод сортировки основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов n-2 сравнений. Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец при помощи всего n-1 сравнений мы можем построить дерево, как показано на рис.1, выбора и определит корень, как наименьший ключ. На втором шаге мы спускаемся по пути, указанном наименьшим ключом, и исключаем его, последовательно заменяя либо на "дыру" (или ключ бесконечность), либо на элемент, находящийся на противоположной ветви промежуточного узла Элемент оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся и может быть исключен. После n таких шагов дерево становится пустым (т.е. состоит из "дыр"), и процесс сортировки закончен.
При сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов; в конечном счете, для хранения возросшего объема информации нужно строить некую древовидную структуру. Также желательно избавиться от необходимости в дырах, которые в конце заполняют дерево и приводят к большому числу ненужных сравнений. Механизм сортировки методом бинарного дерева отображен на рисунке 7.
Рисунок 7. Сортировка бинарным деревом
2.4 Пирамидальная сортировка
Пирамида определяется как последовательность ключей
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 и отклонения от этого значения сравнительно малы.
2.5 Сортировка Шелла
На рисунке 9 продемонстрирована сортировка методом Шелла:
Рисунок 9. Сортировка Шелла
На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В нашем примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2-сортировкой. Наконец на третьем проходе все элементы сортируются обычной 1-сортировкой включением.
На каждом шаге в сортировке участвует либо сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок. Очевидно, что этот метод дает упорядоченный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки. Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через
h1, h2,..., hn с условиями ht=1, hi+1 < hi.
Каждая h-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включения было простым, используется ба
2.6 Сложная сортировка обменом (сортировка Хоора)
Сортировка Хоора основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Реализуется она на основе следующего алгоритма: выбирается любой произвольный элемент массива, называемый медианой далее массив просматривается слева направо до тех пор, пока не будет найден элемент больший выбранного; а затем массив просматривается справа налево, пока не будет найден элемент меньший выбранного. Найденные элементы меняются местами. Затем продолжается процесс "просмотра с обменом", пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами.
Ожидаемое число обменов равно приблизительно n / 6. Быстрая сортировка все же имеет свои "подводные камни". Прежде всего, при небольших значениях n ее эффективность невелика, как и у всех усовершенствованных методов. Ее преимущество по сравнению с другими усовершенствованными методами заключается в том, что для сортировки уже разделенных небольших подмассивов легко можно применить какой-либо простой метод.
2.7 Общий анализ приведенных сортировок
Приведем выводы по простым методам сортировки:
Время сортировки пропорционально квадрату размерности массива
Более точные оценки производительности простых методов сортировки показывают, что наиболее быстрой
является сортировка вставками, а наиболее медленной
− сортировка обменом.
Несмотря на плохое быстродействие, простые алгоритмы сортировки следует применять при малой размерности сортируемого массива.
Наряду с простыми методами сортировки существуют более сложные, обеспечивающие время сортировки пропорциональное .
При больших размерностях массива они обеспечивают существенный выигрыш.
Сравним простые и сложные методы сортировки по производительности:
Таблица 1. Сравнительные показатели производительности различных методов сортировки массивов
| Простые методы сортировки |
|||
| Метод сортировки
|
Время сортировки для размера 256, миллисекунд
|
Время сортировки для размера 512, миллисекунд
|
Соотношение методов по производительности (относительное время сортировки)
|
| Вставками (метод простых вставок) |
356 |
1444 |
1 |
| Выбором |
509 |
1956 |
1.3 |
| Обменом (пузырек) |
1026 |
4054 |
3 |
| Сложные методы сортировки |
|||
| Обменом (Хоора) |
60 |
116 |
1 |
| Выбором (с помощью двоичного дерева |
110 |
241 |
1.7 |
| Вставками (Шелла) |
127 |
349 |
2.1 |
Из приведенных в таблице данных следует, в частности, для относительно небольшого массива в 512 элементов:
Худшая по производительности из простых сортировок (сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоора.
Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4.2 раза чем худшая по производительности из сложных сортировок (сортировка Шелла).
При увеличении размера массива указанные выше эффекты проявляются в большей степени
2.8 Теоретическое сравнение сортировок методом простых вставок и методом пузырька
Выполним по рекомендованной литературе теоретическое сравнение алгоритмов сортировок, рассматриваемых в данном курсовом проекте. Основным критерием сравнения сортировок является их эффективность, то есть число сравнений и число пересылок. Данные показатели также влияют на время сортировки. Укажем основные формулы, использующиеся для вычисления эффективности данных сортировок:
− число сравнений ключей элементов при i-ом просеивании;
−минимальное число сравнений ключей;
− максимальное число сравнений ключей;
− среднее число сравнений ключей;
− число пересылок (присваиваний) элементов при i-ом просеивании;
− минимальное число пересылок
− максимальное число пересылок
− среднее число пересылок
− размер массива;
Рассмотрим сортировку методом простых вставок
Рассмотрим сортировку методом пузырька
На основе данных методических формул составим сравнительную таблицу для сортировок методом простых вставок и методом пузырька:
Таблица 2. Сравнительный анализ сортировок методом простых вставок и методом пузырька
| Размер массива |
Метод простых вставок |
Метод пузырька |
||
| Число сравнений ключей (среднее значение) |
Число пересылок (среднее значение) |
Число сравнений ключей (среднее значение) |
Число пересылок (среднее значение) |
|
| 32 |
263 |
329 |
256 |
384 |
| 64 |
1039 |
1163 |
1024 |
1536 |
| 128 |
4127 |
4379 |
4096 |
6144 |
| 256 |
16447 |
16953 |
16384 |
24576 |
| 512 |
65663 |
131835 |
65536 |
98304 |
| 1024 |
262399 |
264443 |
262144 |
393216 |
На основе полученных в таблице 2 значений составим сравнительные графики, для числа сравнений ключей и для числа пересылок по обоим методам сортировки:
Рисунок 10. Графики числа сравнений ключей: число сравнений ключей П - для метода пузырька, число сравнений ключей В - для метода простых вставок.
На основе полученных графиков можно сказать, что число сравнений ключей в сортировке методом пузырька число сравнений больше, чем в сортировке методом вставок. Следовательно по данному критерию эффективность сортировки методом простых вставок выше, чем методом пузырька.
Рисунок 11. Графики числа пересылок в сортировках: число пересылок П - для метода пузырька, число пересылок В - для метода простых вставок.
Основываясь на полученных графиках можно сказать, что при малых значениях размерности массива число пересылок для обоих методов примерно одинаково. При относительно больших размерах массива (от 512 и более) число пересылок в методе
пузырька возрастает быстрее, чем в методе простых вставок. Следовательно, эффективность метода вставок выше по данной характеристике.
Ссылаясь на таблицу 1 можно также отметить, что сортировка методом пузырька требует больше времени, чем сортировка методом вставок.
Из чего следует, что в целом сортировка методом простых вставок эффективнее сортировки методом пузырька.
2.9 Разработка и программирование алгоритма сортировки методом простых вставок
Алгоритм сортировки методом простых вставок рассмотрен в разделе 2.2 курсового проекта. Для того, чтобы запрограммировать данный алгоритм сортировки представим его сначала в виде блок-схемы для более наглядного отображения его функционирования:
i, j - счетчики;
t - переменная в которой запоминается вставляемый элемент;
a - массив элементов;
n - количество элементов в массиве а;
Блок-схема 1. Алгоритм сортировки методом простых вставок
На первом шаге алгоритма объявляются переменные счетчики i и j, использующиеся в циклах. А также переменная t в которой будет запоминаться очередной элемент из неупорядоченной части массива для вставки в упорядоченную часть.
На втором шаге начинается цикл с параметром, в котором осуществляется перебор всех элементов массива с первого по последний. Нулевой элемент массива, фактически являющийся первым, на данном этапе является единственным элементом упорядоченной части массива, относительно которого будут вставляться все последующие элементы из неупорядоченной части массива.
Соответствующий итерации элемент из неупорядоченной части запоминается в переменной t, после чего в теле цикла задается еще один цикл с параметром, в котором осуществляется поиск места для подстановки элемента в упорядоченную часть. Осуществляется перебор элементов начиная с нулевого в упорядоченной части, так как массив упорядочивается по возрастанию проверяется условие меньше ли выбранный элемент других элементов из упорядоченной части. Так как подобный перебор должен каждый раз начинаться с нулевого элемента упорядоченной части, то выполняется декремент счетчика j. Если найдено место для подстановки, удовлетворяющее условиям, то осуществляется вставка и сдвиг элементов упорядоченной части.
На основе данной блок-схемы можно разработать функцию, выполняющую сортировку массива методом простых вставок на языке программирования C++:
void insert (int *a, int n) // ФУНКЦИЯ ВСТАВОК
{
int i, j, t; // объявление переменных
for (i=1; i<n; i++)
{
t=a [i] ; // запоминается элемент для вставки
for (j=i-1; j>=0 && t<a [j] ; j--) // ищем место для вставки
a [j+1] =a [j] ; // сдвиг на одну позицию
a [j+1] =t;
}
}
3. Разработка и программирование алгоритма сортировки методом пузырька
Алгоритм сортировки массива методом пузырька описан в разделе 2.3, для наглядного отображения принципа действия отобразим его в виде блок схемы.
При этом используем обозначения из предыдущей блок-схемы, описывающей алгоритм сортировки методом простых вставок.
Первый шаг алгоритма такой же как и в методе простых вставок − объявляются переменные счетчики i, j и переменная t, в которой запоминается элемент при перестановке. На втором шаге начинается цикл с параметром в котором осуществляется перебор всех элементов массива с нулевого по предпоследний, так как последний элемент уже не с чем будет сравнивать. В теле цикла задается еще один цикл с параметром, содержащий условие, в котором сравниваются пара соседних элементов. Если условие выполняется, то осуществляется перестановка элементов, если не выполняется − начинается следующая итерация первого цикла с параметром.
На основе данной блок-схемы можно запрограммировать функцию, выполняющую сортировку массива методом пузырька.
Блок-схема 2. Алгоритм сортировки методом пузырька
void bubble (int *a, int n) // функция пузырька
{
int i,j,t; // объявление переменных
for (i = 0; i <= n-1; i++)
{
for (j = 0; j <= n-2-i; j++)
{
if (a [j] >a [j+1]) // сравниваем пару соседних элементов
{
t = a [j] ; // и меняем их местами если это требуется
a [j] = a [j+1] ;
a [j+1] = t;
}
}
}
}
4. Тестирование разработанных функций сортировки методом простых вставок и методом пузырька
В ходе работы над курсовым проектом было разработано 2 функции: функция сортировки массива методом простых вставок, и функция сортировки массива методом пузырька. Так же в разработанной программе использована функция подсчета времени работы программы clock (), содержащаяся в библиотеке time. h. Массив формируется автоматически с помощью встроенной функции randomize (), пользователю нужно лишь задать число элементов в массиве и выбрать метод сортировки. После чего будет выполнена сортировка выбранным методом, выведен на экран упорядоченный массив и время сортировки в миллисекундах.
Для тестирования работы программы совершим несколько прогонов с разными значениями. В качестве отчета о работе программы приведены скриншоты:
Рисунок 12. Скриншот работающей программы, сортировка методом простых вставок
Рисунок 13. Скриншот работающей программы, сортировка методом пузырька
Как видно на скриншотах программа успешно выполняет сортировку методом простых вставок и методом пузырька и выводит время сортировки.
5. Экспериментальное сравнение разработанных алгоритмов сортировки
Для экспериментального сравнения эффективности работы методов сортировок нужно определить время сортировки − в данном случае оно является главным показателем эффективности. В таблице 3 указано время сортировки соответствующее определенному количеству элементов массива, определенное экспериментально для каждого метода сортировки.
Таблица 3. Время сортировки
| Количество элементов массива |
Время сортировки для метода простых вставок, мс |
Время сортировки для метода пузырька, мс |
| 5 |
237 |
245 |
| 10 |
248 |
267 |
| 15 |
253 |
272 |
| 20 |
259 |
294 |
| 30 |
277 |
311 |
| 40 |
279 |
320 |
| 64 |
346 |
368 |
| 128 |
659 |
702 |
| 256 |
876 |
912 |
| 512 |
910 |
975 |
| 1024 |
953 |
1034 |
На основе данной таблицы построены графики для экспериментального анализа эффективности методов сортировки.
Рисунок 14. Графики зависимости времени сортировки от количества элементов массива
Опираясь на данные графики можно сделать вывод, что общее время сортировки для метода простых вставок меньше, чем для метода пузырька. Следовательно, сортировка методом простых вставок является более эффективной, чем сортировка методом пузырька.
Заключение
В ходе курсовой работы был проведен обзор существующих алгоритмов сортировки, в том числе оценка их эффективности. Был сделан вывод, что методы сложных сортировок (сортировки использующие копирование массива), более эффективны в целом, чем методы простых сортировок. Причем самая эффективная из простых сортировок менее эффективна, чем худшая по производительности из сложных сортировок.
Также было выполнено теоретическое сравнение эффективности алгоритмов сортировок, рассматриваемых в рамках курсового проекта, построены соответствующие графики. В ходе теоретического сравнения было выявлено, что сортировка методом вставок эффективнее сортировки методом пузырька, благодаря меньшему числу сравнений ключей и меньшему количеству пересылок.
Были разработаны функции сортировки методом простых вставок (insert) и методом пузырька (bubble). Данные функции интегрированы в разработанное приложение, с помощью которого можно создать массив с заданным количеством элементов, отсортировать его любым из рассмотренных в курсовом проекте методом сортировки и узнать время сортировки массива.
С помощью данного приложения был проведен экспериментальный анализ сортировок методом простых вставок и методом пузырька, подтвердивший результаты теоретического сравнения эффективности данных сортировок. По данным экспериментального анализа в среднем сортировка методом простых вставок занимает меньше времени, чем сортировка методом пузырька. Вследствие этого можно сказать, что сортировка методом простых вставок эффективнее, чем сортировка методом пузырька.
Список литературы
1. Лекции по предмету "Программирование языков высшего уровня"
2. "Программирование и основы алгоритмизации" - В.Г. Давыдов - изд. "Высшая школа", 2005.
3. "Основы алгоритмизации и программирования" - О.Л. Голицына, И.И. Попов - изд. "ФОРУМ-ИНФРА-М", 2006.
4. "Программирование на языке высокого уровня" - Т.А. Павловская - изд. "Питер", 2004.
Приложение
(листинг рабочего кода разработанного приложения)
#pragma argsused
#include <iostream. h>
# include <time. h>
void insert (int *a, int n) // ФУНКЦИЯ ВСТАВОК
{
int i, j, t; // объявление переменных
for (i=1; i<n; i++)
{
t=a [i] ; // запоминается элемент для вставки
for (j=i-1; j>=0 && t<a [j] ; j--) // ищем место для вставки
a [j+1] =a [j] ; // сдвиг на одну позицию
a [j+1] =t;
}
}
void buble (int *a, int n) // функция пузырька
{
int i,j,t; // объявление переменных
for (i = 0; i <= n-1; i++)
{
for (j = 0; j <= n-2-i; j++)
{
if (a [j] >a [j+1]) // сравниваем пару соседних элементов
{
t = a [j] ; // и меняем их местами если это требуется
a [j] = a [j+1] ;
a [j+1] = t;
}
}
}
}
int main (int argc, char* argv [])
{
char b;
int n;
typedef long clock_t; // тип данных времени
clock_t t; // t - время выполнения программы
char str1 [100] = "Введите количество элементов для сортировки: ";
char str2 [100] ;
char str3 [100] ;
CharToOem (str1, buf);
cout<<buf<<endl;
cin>>n;
int* a=new int; // создание, указание кол-ва элементов
randomize (); // и заполнение массива
for (int i=0; i<=n; i++)
a [i] =random (50) - 30;
strcpy (str1,"Первичный массив: ");
CharToOem (str1, buf);
cout<<buf<<endl;
for (int i=0; i<n; i++)
{
cout<<" a ["<<i<<"] ="<<a [i] <<' ';
if (! ( (i+1)%5)) cout << "n"; // массив выводится по 5 значений в строке
};
cout<<endl;
strcpy (str1,"Выберите тип сортировки: ");
strcpy (str2,"1. Сортировка методом простых вставок");
strcpy (str3,"2. Сортировка методом пузырька ");
CharToOem (str1, buf);
CharToOem (str2, buf1);
CharToOem (str3, buf2);
cout<<buf<<endl
<<buf1<<endl
<<buf2<<endl;
cin>>b;
strcpy (str1,"Отсортированные элементы: ");
CharToOem (str1, buf);
cout<<buf<<endl;
if (b='1')
{
insert (a,n); // вызов функции сортировки
}
if (b='2')
{
buble (a,n); // вызов функции
}
for (int i=0; i<n; i++)
{
cout<<" a ["<<i<<"] ="<<a [i] <<' ';
if (! ( (i+1)%5)) cout << "n";
}
cout<<endl; // подсчёт времени выполнения программы
strcpy (str1,"Время сортировки в мс: ");
CharToOem (str1, buf);
cout<<buf<<endl;
t= (clock () /CLOCKS_PER_SEC) * 60; // функция clock () возвращает время исп программы
cout<<t; // как значение типа clock_t объявленного ранее это // значение можно перевести в секунды
// поделив на определенную в библиотеке time. h константу CLOCKS_PER_SEC
getchar ();
getchar ();
return 0; }