Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное агентство по образованию Российской Федерации
Самарский государственный аэрокосмический университет
Кафедра Радиоэлектроники и Системотехники
сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька
Пояснительная записка к курсовой работе
Пояснительная записка 34 с., 14 рис.,2 блок-схемы, 3 табл., 4 источника
АЛГОРИТМЫ, ПРОГРАММИРОВАНИЕ, С++, СОРТИРОВКА МЕТОДОМ ВСТАВОК, СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА, СРАВНЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ
Объектом исследования является алгоритмы сортировки.
Цель работы - описать, разработать и запрограммировать два алгоритма сортировки по указанному методу: первый алгоритм - сортировка методом простых вставок, второй - сортировка методом пузырька. Протестировать программу и выполнить экспериментальное сравнение разработанных алгоритмов сортировки, выявив зависимость среднего времени сортировки от числа сортируемых элементов. Построить графики.
В процессе работы были созданы две функции, осуществляющие сортировку любого количества элементов, первый - методом простых вставок, второй - на основе сортировки таблицы адресов.
12 42 44 18 06 55 67 94
12 42 18 06 44 55 67 94
12 18 06 42 44 55 67 94
12 06 18 42 44 55 67 94
06 12 18 42 44 55 67 94
Рисунок 6. Пример сортировки массива простым обменом
Эффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное ? size -1, а среднее ? size/2.
Время сортировки для размера 256, миллисекунд
Время сортировки для размера 512, миллисекунд
Соотношение методов по производительности ( относительное время сортировки )
Выбором (с помощью двоичного дерева
Из приведенных в таблице данных следует, в частности, для относительно небольшого массива в 512 элементов:
Худшая по производительности из простых сортировок (сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоора.
Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4.2 раза чем худшая по производительности из сложных сортировок (сортировка Шелла).
При увеличении размера массива указанные выше эффекты проявляются в большей степени
Число сравнений ключей (среднее значение)
Число сравнений ключей (среднее значение)
На основе полученных в таблице 2 значений составим сравнительные графики, для числа сравнений ключей и для числа пересылок по обоим методам сортировки:
Рисунок 10. Графики числа сравнений ключей: число сравнений ключей П - для метода пузырька, число сравнений ключей В - для метода простых вставок.
На основе полученных графиков можно сказать, что число сравнений ключей в сортировке методом пузырька число сравнений больше, чем в сортировке методом вставок. Следовательно по данному критерию эффективность сортировки методом простых вставок выше, чем методом пузырька.
Рисунок 11. Графики числа пересылок в сортировках: число пересылок П - для метода пузырька, число пересылок В - для метода простых вставок.
Основываясь на полученных графиках можно сказать, что при малых значениях размерности массива число пересылок для обоих методов примерно одинаково. При относительно больших размерах массива (от 512 и более) число пересылок в методе
пузырька возрастает быстрее, чем в методе простых вставок. Следовательно, эффективность метода вставок выше по данной характеристике.
Ссылаясь на таблицу 1 можно также отметить, что сортировка методом пузырька требует больше времени, чем сортировка методом вставок.
Из чего следует, что в целом сортировка методом простых вставок эффективнее сортировки методом пузырька.
Время сортировки для метода простых вставок, мс
Время сортировки для метода пузырька, мс
На основе данной таблицы построены графики для экспериментального анализа эффективности методов сортировки.
Рисунок 14. Графики зависимости времени сортировки от количества элементов массива
Опираясь на данные графики можно сделать вывод, что общее время сортировки для метода простых вставок меньше, чем для метода пузырька. Следовательно, сортировка методом простых вставок является более эффективной, чем сортировка методом пузырька.
1. Лекции по предмету "Программирование языков высшего уровня"
2. "Программирование и основы алгоритмизации" - В.Г. Давыдов - изд. "Высшая школа", 2005.
3. "Основы алгоритмизации и программирования" - О.Л. Голицына, И.И. Попов - изд. "ФОРУМ-ИНФРА-М", 2006.
4. "Программирование на языке высокого уровня" - Т.А. Павловская - изд. "Питер", 2004.
Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки. реферат [189,8 K], добавлен 06.12.2014
Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки. курсовая работа [161,7 K], добавлен 17.12.2015
Определение понятия, видов и задач сортировки. Рассмотрение основ построения простых и улучшенных алгоритмов сортировки, анализ числа операций. Линейная и пирамидальная организация данных. Основные правила нижней оценки числа операций в алгоритмах. презентация [274,5 K], добавлен 19.10.2014
Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных. лабораторная работа [1,2 M], добавлен 23.07.2012
Анализ структуры топологической сортировки в программной среде. Метод топологической сортировки с помощью обхода в глубину. Программа, реализующая топологическую сортировку методом Демукрона. Создание карты сайта и древовидная система разделов. курсовая работа [1,3 M], добавлен 22.06.2011
Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи. реферат [20,7 K], добавлен 20.05.2010
Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы. курсовая работа [203,8 K], добавлен 03.12.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька курсовая работа. Программирование, компьютеры и кибернетика.
Режим Рабочего Времени Бортпроводника Реферат
Узнать Результаты Контрольной Работы 2022 Огэ
Реферат по теме Классификация регионов
Реферат по теме Двигатель внутреннего сгорания
Отчет по практике по теме Печатное полиграфическое оборудование
Реферат Образец Ямк
Київська Русь Культура Реферат
Реферат: Taming Of The Shrew Inside Essay Research
Эссе Осенний Лес
Итоговая Контрольная Работа За Курс 10
Доклад по теме Борьба патрициев и плебеев в Древнем Риме. Изгнание Тарквиния Гордого
Реферат по теме Деньги и денежные средства
Реферат по теме Эволюция позиционирования
Диссертация Доктора Экономических Наук
Статья: Река Черная - тайна и загадка Вьетнама
Сочинение Недоросль Воспитание И Образование
Реферат: Актуальность темы исследования. В «Морской доктрине Российской Федерации на период до 2022 г.» подчеркивается, что в настоящее время Атлантическое региональное
Реферат по теме Альтернативные социалистические течения, радикальные и национальные идеологии
Дипломная работа по теме Проектирование тепловых конденсационных электрических станций
Реферат: Особенности правового регулирования договора аренды предприятия
Гражданское правоотношение - Государство и право курсовая работа
Культура Древней Руси - История и исторические личности контрольная работа
Судово-бухгалтерська експертиза обліку основних засобів - Бухгалтерский учет и аудит контрольная работа