Обоснование к разрабатываемой
Сравнительный анализ сортировки методом вставок и пузырька
Содержание
Введение. 3
1. Анализ поставленной задачи и постановка задачи на проектирование. 5
1.1 Поиск, анализ и выбор основных вопросов, подлежащих реализации. 5
1.2 Выбор программного обеспечения по реализации ИТ. 5
1.3 Обоснование требований к разрабатываемой ИТ. 6
2. Обзор алгоритмов сортировки. 8
2.1 Характеристика основных аспектов сортировки. 8
2.2 Сортировка массива простыми включениями. 13
2.3 Сортировка массива простым обменом («метод пузырька») 14
2.4 Сортировка массива сложным выбором (с помощью двоичного дерева) 15
2.5 Пирамидальная сортировка. 16
2.6 Сортировка Шелла. 18
2.7 Сложная сортировка обменом (сортировка Хоора) 19
3. Общий анализ приведенных сортировок. 21
3.1 Выводы по простым методам сортировки. 21
3.2 Теоретическое сравнение сортировок методом простых вставок и методом пузырька 22
3. 4 Разработка и программирование алгоритма сортировки методом простых вставок 25
3.5 Разработка и программирование алгоритма сортировки методом пузырька 27
3.6 Тестирование разработанных функций сортировки методом простых вставок и методом пузырька. 28
3.7 Экспериментальное сравнение разработанных алгоритмов сортировки 29
Заключение. 32
Список использованных источников. 33
Приложение. 35
Введение
При внутренней сортировке массивы располагаются в оперативной памяти ЭВМ, что обеспечивает быстрый произвольный доступ к данным.
|
|
|
При внешней сортировке файлы хранятся в более «медленной», но более вместительной внешней памяти, т. е. на запоминающих устройствах с механическим передвижением (магнитных дисках и других носителях).
Критериями оценки методов сортировки являются:
1) количество операций сравнения пар ключей
2) число перестановок элементов
3) экономное использование памяти
Цель курсовой работы:
1) систематизация, углубление и активное применение знаний по программированию в среде С++
2) рассмотреть основные алгоритмы сортировки
3) разработать, протестировать и проанализировать алгоритмы сортировки методом простых вставок и методом пузырька
Оценить производительность данных алгоритмов и сравнить их между собой по различным характеристикам
Актуальность: С помощью ЭВМ можно решать самые разные задачи, в том числе автоматически выполнять требуемую сортировку данных. Сортировка может требоваться в различных ситуациях, например, когда нужно отобразить визуально распределение данных. Для различных данных существуют определенные методы сортировок повышающие производительность и скорость сортировки именно для этого типа данных.
|
|
|
Рассматриваемые в данной работе сортировки методы сортировки являются относительно простыми, и хотя их эффективность ниже чем у более сложных и совершенных методов, но они так же имеют ряд преимуществ, и к тому же лежат в основе большинства других методов сортировки.
Новизна: Рассматриваемые методы сортировок в силу своей простоты особенно хорошо подходят для изучения свойств большинства принципов сортировки, программы, основанные на данных методах легки для понимания и коротки (это также позволяет экономить память, занимаемую программой). Так же важно отметить, что, хотя сложные алгоритмы требуют меньшего числа операций, но эти операции являются более сложными. Поэтому при относительно малом количестве сортируемых элементов простые методы сортировки работают достаточно быстро.
Поставленной задачи постановка задачи на
Поиск, анализ выбор основных вопросов, реализации
В с целями курсового проекта, начать проектирование анализ требуемых для программ.
В необходимо отметить типы и сортировок, их характеристики. Это для выделения отличий рассматриваемых курсовом проекте сортировок других существующих методов . По рекомендованной выполнить теоретическое алгоритмов сортировок, в рамках проекта. Построить -схемы, наглядно принцип работы сортировок методом вставок и «пузырька».
|
|
|
Далее описать, разработать запрограммировать алгоритмы сортировки перестановки данных в курсовом . Протестировать программы ( должны сортироваться) отобразить это в . Выполнить сравнительный работы двух сортировки, и зависимость среднего сортировки от сортируемых элементов, график, отображающий зависимость.
Выбор обеспечения по ИТ
При программ для сортировок массивов использован язык С++. Это из широко языков программирования, можно использовать написания программ, в операционной Windows. Среда C++ Builder 6- сложный механизм, высокоэффективную работу
Интегрированная среда C++ Builder собой многооконную . Вид интегрированной разработки (интерфейс) различаться в от настроек. стандартных окон, экране могут присутствовать другие окна, отображаемые вызове соответствующих , например, Image (Редактор изображений). C++ Builder (не главное) можно , убирать с , а также их размеры.
на наличие окон, C++ является одно- средой, т. . позволяет одновременно только с приложением (проектом ). Название проекта выводится в заголовка главного в верхней экрана.
|
|
|
Если главное окно, происходит минимизация всего C++ Builder , соответственно, всех окон. При главного окна с C++ прекращается.
Borland ++ Builder 6, вобрав себя всё самое от предыдущих , предоставляет ряд возможностей. Так, , стал более и современным среды программирования, C++ Builder учитывают архитектуру процессоров, существенно возможности отладчика.
C++ Builder 6 работать в операционных систем Windows 95 до Windows . Особенных требований компьютеру система не , за исключением , что процессор быть типа , оперативной памяти — менее 32 Мбайт и количество свободной памяти.
Обоснование к разрабатываемой
Касательно выбора и прочих представления курсового — шрифт выбран 14 Times New для удобства представленной информации. в курсовом используются таблицы рисунки для более представления и информации, обозначенные подписями и .
Все рисунки, , схемы и возможная информация, в курсовом , имеют явные и подписи своему размещению, потому их не никакого труда.
Алгоритмов сортировки
Основных аспектов
Сортировка — это перестановки объектов множества в порядке. Цель — облегчить последующий элементов в множестве. Поэтому сортировки присутствуют многих задачах прикладного .
Рассмотрим алгоритмы «на месте», есть те алгоритмы которых не используется массива.
Удобной эффективности алгоритмов «на месте» число необходимых в ходе и число пересылок элементов.
алгоритмы сортировки порядка
сравнений, N — число , а С — необходимых сравнений.
рассмотрим простые методы , которые требуют сравнений порядка
сортировки «на » можно разбить три основных класса:
1) выбором
2) сортировка
3) сортировка обменом
сортировке выбором выбирается с наибольшим ключа и местами с . Затем то самое повторяется для -1 элемента. Найденный с наибольшим ключа меняется предпоследним элементом т. д. ( 2.1).
Рисунок 2.1 Сортировка выбором
В включениями элементы на уже и неупорядоченную . В начале часть содержит один элемент. элемент из неупорядоченной части на подходящее в упорядоченную . При этом часть удлиняется один элемент, а — укорачивается. Сортировка при исчезновении части (рисунок 2.2).
2.2 Сортировка простыми
Основная характеристика обменом — перестановка двух соседних , если они не так, требует отсортированный .
Рисунок 2.3 Сортировка обменом
В классификации существуют алгоритмы. Они сложностью, быстротой , последовательностью операций.
:
1) сортировка вставками;
2) сортировка;
3) корневая ;
4) пирамидальная сортировка;
5) слиянием;
6) быстрая ;
7) сортировка Шелла др.
Рассмотрим подробнее типы и сортировок (сначала сортировки затем сложные).
Сортировка простым выбором - основан на правиле:
Выбирается с наибольшим ключа
Он местами с элементом arr [-1]. Затем эти повторяются с первыми s-1 , затем — с -2 первыми элементами т. д. тех пор, пока останется только первый — наименьший. Пример методом простого показан на 2.4:
Рисунок 2.4 Сортировка простым выбором
сортировки простым . Число сравнений не зависит начального порядка ключей. сравнения выполняется теле цикла с переменной kи числом повторений /2. Этот цикл, свою очередь, находится теле цикла с переменной L числом повторений size ?1. образом, число
С= (size ?1) * ?½
Число пересылок, , зависит от порядка ключей. принять, что сравнения в цикла по дает результат «истина» половине случаев, то число пересылок этом цикле равно /4. Цикл по , как указывалось , выполняется size ?1 и в цикла выполняется пересылки и по k. учетом этого число :
М= (3+ size/4) * ( ?1)
Получаем, что сортировке простым и число , и число пропорционально.
Дата добавления: 2018-04-15; просмотров: 450; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!