Сортировка массивов. Сравнение эффективности различных методов сортировок
ВВЕДЕНИЕ
На данный момент существует множество алгоритмов сортировки данных. Зачастую выбор алгоритма решения задачи зависит от структуры сортируемых данных. В случае сортировки эта зависимость имеет большое значение, и методы сортировки обычно разделяют на две категории:
1.Сортировка массивов (внутренняя сортировка);
2.Сортировка последовательных файлов (внешняя сортировка).
При внутренней сортировке массивы располагаются в оперативной памяти ЭВМ, что обеспечивает быстрый произвольный доступ к данным.
При внешней сортировке файлы хранятся в более "медленной", но более вместительной внешней памяти, т.е. на запоминающих устройствах с механическим передвижением (магнитных дисках и других носителях).
Критериями оценки методов сортировки являются:
•количество операций сравнения пар ключей;
•число перестановок элементов;
•экономное использование памяти.
Цель курсовой работы:
•систематизация, углубление и активное применение знаний по программированию в среде С++
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ3
1. АНАЛИЗ ПОСТАВЛЕННОЙ ЗАДАЧИ И ПОСТАНОВКА ЗАДАЧИ НА ПРОЕКТИРОВАНИЕ5
1.1 Поиск, анализ и выбор основных вопросов, подлежащих реализации5
1.2 Выбор программного обеспечения по реализации ИТ6
2. ОБЗОР АЛГОРИТМОВ СОРТИРОВКИ8
2.1 Сортировка массива простым выбором10
2.2 Сортировка массива простыми включениями12
2.3 Сортировка массива простым обменом ("метод пузырька")14
2.4 Сортировка массива сложным выбором (с помощью двоичного дерева)15
2.5 Пирамидальная сортировка17
2.6 Сортировка Шелла19
2.7 Сложная сортировка обменом (сортировка Хоора)21
2.8 Общий анализ приведенных сортировок23
2.9 Теоретическое сравнение сортировок методом простых вставок и методом пузырька25
3. РАЗРАБОТКА И ПРОГРАММИРОВАНИЕ АЛГОРИТМОВ СОРТИРОВКИ29
3.1 Разработка и программирование алгоритма сортировки методом простых вставок29
3.2 Разработка и программирование алгоритма сортировки методом пузырька31
4. ТЕСТИРОВАНИЕ РАЗРАБОТАННЫХ ФУНКЦИЙ СОРТИРОВКИ МЕТОДОМ ПРОСТЫХ ВСТАВОК И МЕТОДОМ ПУЗЫРЬКА33
5. ЭКСПЕРИМЕНТАЛЬНОЕ СРАВНЕНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ СОРТИРОВКИ35
ЗАКЛЮЧЕНИЕ37
СПИСОК ЛИТЕРАТУРЫ38
Приложение А39
Приложение Б40
Приложение В41
СПИСОК ЛИТЕРАТУРЫ
1.Лекции по предмету "Программирование языков высшего уровня"
2."Программирование и основы алгоритмизации" - В.Г. Давыдов - изд. "Высшая школа", 2005.
3."Основы алгоритмизации и программирования" - О.Л. Голицына, И.И. Попов - изд. "ФОРУМ-ИНФРА-М", 2006.
4."Программирование на языке высокого уровня" - Т.А. Павловская - изд. "Питер", 2004.
Поэтому общее число сравнений и пересылок есть:
Cmin = n-1 Mmin = 2 (n-1)
Cср. = (n2+n-2) /4 Mср. = (n2+9n-10) /4
Cmax = ( (n2+n) - 1) /2 Mmax = (n2+3n-4) /2.
Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a [1],…, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения.
2.3 Сортировка массива простым обменом ("метод пузырька")Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Пример сортировки методом "пузырька" приведен на рисунке 6.