Анализ некоторых видов сортировок
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
преимуществ:
.эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
.эффективен на наборах данных, которые уже частично отсортированы;
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
.может сортировать список по мере его получения;
использует O(1) временной памяти, включая стек.
Минусом же является высокая сложность алгоритма
Описание:
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.
Анализ алгоритма
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим - массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных
Сортировка выбором
Алгоритм может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае ?(n2), предполагая что сравнения делаются за постоянное время.
Алгоритм
Шаги алгоритма:
.находим минимальное значение в текущем списке
.производим обмен этого значения со значением на первой неотсортированной позиции
.теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Анализ сортировки
К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). В лучшем случае (когда исходный
массив уже упорядочен) потребуется поменять местами только n-1элементов,а каждая операция обмена требует три операции пересылки.
Пирамидальная сортировка
Пирамидальная сортировка (англ. Heapsort, Сортировка кучей) - алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за ?(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Идея алгоритма
Пирамида - двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.
Заполнив дерево элементами в произвольном порядке, можно легко его отсортировать (легче, чем исходный список элементов), превратив в пирамиду.
Самый большой элемент пирамиды находится в её вершине.
Отделяем вершинный элемент, и записываем его в конец результирующего массива.
На место вершинного элемента записываем элемент из самого нижнего уровня дерева.
Восстанавливаем (пересортировываем) пирамиду.
Самый большой элемент из оставшихся снова в вершине. Снова отделяем его и записываем его в качестве предпоследнего элемента результата, и так далее...
Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исходном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается начиная с конца массива на освободившиеся от пирамиды места.
Достоинства и недостатки
Достоинства
.Имеет доказанную оценку худшего случая .
.Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки
.Сложен в реализации.
.Неустойчив - для обеспечения устойчивости нужно расширять ключ.
.На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
.На одном шаге выборку приходится делать хаотично по всей длине массива - поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
Технологический раздел
Блок-схема программы
В курсовой работе использовались следующие стандартные заголовочные файлы:
- заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++. Он включён в стандартную библиотеку C++. Название образовано от Input/Output Stream (поток ввода-вывода). В языке C++ и его предшественнике, языке программирования Си, нет встроенной поддержки ввода-вывода, вместо этого используется библиотека функций. iostream управляет вводом-выводом, как и stdio.h в Cи. iostream использует объекты cin, cout, cerr и clog для передачи информации в и из стандартных потоков ввода, вывода, ошибок (без буферизации) и ошибок (с буферизацией) соответственно. Являясь частью стандартной библиотеки C++, эти объекты также являются частью стандартного пространства имён - std.
- заголовочный файл стандартной библиотеки языка Си, который содержит в себе функции, занимающи?/p>