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

Федеральное агентство по образованию Российской Федерации

Самарский государственный аэрокосмический университет

Филиал в г. Тольятти

Кафедра Радиоэлектроники и Системотехники

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

Пояснительная записка к курсовой работе

Руководитель

проекта Репина И.Г.

Исполнитель

студент гр.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 Поиск, анализ и выбор основных вопросов, подлежащих реализации

В соответствии с целями данного курсового проекта, возможно начать проектиров

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать