Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька (стр. 4 из 5)
Рисунок 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). Данные функции интегрированы в разработанное приложение, с помощью которого можно создать массив с заданным количеством элементов, отсортировать его любым из рассмотренных в курсовом проекте методом сортировки и узнать время сортировки массива.
С помощью данного приложения был проведен экспериментальный анализ сортировок методом простых вставок и методом пузырька, подтвердивший результаты теоретического сравнения эффективности данных сортировок. По данным экспериментального анализа в среднем сортировка методом простых вставок занимает меньше времени, чем сортировка методом пузырька. Вследствие этого можно сказать, что сортировка методом простых вставок эффективнее, чем сортировка методом пузырька.