Сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька
Федеральное агентство по образованию Российской Федерации Самарский государственный аэрокосмический университет Филиал в г. Тольятти Кафедра Радиоэлектроники и Системотехники сравнительный анализ алгоритмов сортировки методом простых вставок и методом пузырька Пояснительная записка к курсовой работе Руководитель проекта Репина И.Г. Исполнитель студент гр.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 или достигнут левый конец готовой последовательности.При этом упорядоченная часть удлиняется на один элемент. Сортировка заканчивается при окончании неупорядоченной части.
Страницы: 1, 2, 3
|
