Анализ некоторых видов сортировок
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Приднестровский государственный университет им. Т.Г. Шевченко
Рыбницкий филиал
Кафедра физики, математики и информатики
Курсовая работа
по дисциплине Программирование на языке высокого уровня C++
на тему
Анализ некоторых видов сортировок
Выполнил:
Лученецкий Роман
Рыбница
г.
Введение
В данной курсовой работе рассмотрены некоторые виды сортировок: вставками, выбором, пузырьком, пирамидальная.
Определим понятие "сортировка" как упорядочение элементов некоторой последовательности (например массивов или динамических списков) в возрастающем или убывающем порядке (в случае равных элементов правильнее сказать - в неубывающем и невозрастающем порядке соответственно). Так мы не будем путать определения в будущем.
Для чего нужна сортировка? Очевидно, что если само понятие содержит слово "упорядочение", то сортировка нужна для создание некого порядка среди данных. Искать же что-либо становиться гораздо удобнее, если мы знаем, где это искать, т.е. порядок расположения. Итак, первое приложение сортировки - создание удобных условий для быстрого поиска данных.
Следующая задача является классической: "Сколько в массиве находиться одинаковых элементов каждого типа?" Допустим, что у нас есть массив анкет о сотрудниках организации и нам надо найти их распределение возрастов (сколько человек имеют 30, 50, 60 лет). Эту задачу легко решить, если отсортировать анкеты по возрасту сотрудников, и затем пройтись по массиву, подсчитывая количество сотрудников с каждым возрастом.
Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве.
В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонных книгах, в ведомостях подоходных налогов, в оглавлениях, в библиотеках, в словарях, на складах, да и почти всюду, где их нужно разыскивать. Даже маленьких детей приучают приводить вещи в порядок, и они сталкиваются с некоторым видом сортировки задолго до того, как узнают что-либо об арифметике.
Сортировки обычно разделяют на две категории: сортировка массивов и сортировка последовательных файлов. Их часто называют внутренней и внешней сортировкой, так, как массивы располагаются во внутренней памяти ЭВМ, а файлы хранятся в более медленной, но более вместительной внешней памяти, т.е. на запоминающих устройствах с механическим передвижением (дисках, лентах).
Цель: исследовать некоторые методы сортировок.
Задачи: изучить литературу по алгоритмам сортировок, составить подпрограммы сортировок, провести анализ и вычислить среднее время каждой сортировки, составить графическое меню.
сортировка алгоритм последовательность подпрограмма
Теоретический раздел
Сортировка пузырьком
Сортировка простыми обменами, сортиро?вка пузырько?м (англ. bubble sort) - простой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, всплывает до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Обратите внимание, что количество повторов во внутреннем цикле уменьшается с каждой итерацией внешнего цикла. Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент будет находиться на N-1 месте. И так далее. Таким образом нет необходимости "обходить" весь массив от начала до конца каждый раз.
Анализ сортировки
При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худшем случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.
Сортировка вставками
Сортировка вставками - простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд