Исследование улучшенных методов сортировки (Предмет: Алгоритмы и структуры данных)

Целью данной курсовой работы является изучения основных алгоритмов улучшенной сортировки массивов данных, сравнение сложности их реализации и производительности.

При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно/.
«Внутренний цикл имеет два условия проверки. Условие "х<item[j]" необходимо для упорядочения элементов. Условия "j>0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки.»
Анализ сортировки Шелла требует решения некоторых сложных математических задач. Время выполнения сортировки Шелла пропорционально n1.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.

Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.
В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве.
Строгие методы сортировки имеют один фатальный недостаток — время их выполнения имеет порядок n2. Это делает сортировку больших объемов данных очень медленной. По существу, в какой-то момент эти алгоритмы становятся слишком медленными, чтобы их применять.
Существует правило: если используемый в программе алгоритм слишком медленный сам по себе, никакой объем ручной оптимизации не сделает программу достаточно быстрой. Решение заключается в применении лучшего алгоритма сортировки.
В курсовой работе описаны методы улучшенной сортировки.
Эти методы являются более совершенными способами сортировки и имеют намного лучшую общую производительность, чем любой из строгих методов.
В данной курсовой работе предложен анализ к каждому из улучшенных методов сортировки массивов.
Таким образом, существующие алгоритмы сортировки массивов значительно различаются по уровню сложности, скорости, устойчивости, требованиям к памяти и другим параметрам. Однако практически каждый алгоритм оказывается наиболее удобным в какой-либо конкретной ситуации.