Мегаобучалка Главная | О нас | Обратная связь  


Теоретическое сравнение сортировок методом простых вставок и методом пузырька




 

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

− число сравнений ключей элементов при 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 можно также отметить, что сортировка методом пузырька требует больше времени, чем сортировка методом вставок.

Из чего следует, что в целом сортировка методом простых вставок эффективнее сортировки методом пузырька.

 

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...
Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация...
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (298)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.012 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7