Содержание
Введение3
1. Понятие сортировки, простые методы сортировки.5
1.1. Понятие и обзор методов сортировки.5
1.2. «Простые» алгоритмы сортировки7
2. Эффективные алгоритмы сортировки21
2.1. Метод Шелла21
2.2. Быстрая сортировка27
Заключение34
Список литературы36
Введение
При разработке алгоритмов программного обеспечения нередко возникает ситуация, когда программа имеет дело с некоторым, иногда достаточно большим, объемом неупорядоченной информации, которую следует упорядочить по определенным признакам. Такие задачи встречаются, когда надо отсортировать скажем массив строк по алфавиту, числовые значения по убыванию или возрастанию.
При решении подобной задачи нередко возникают вопросы производительности и быстродействия. Это актуально для программного обеспечения, которое предназначено для работы с большим объемом данных. В связи с этим уже достаточно давно в теории алгоритмов обсуждаются различные варианты реализации поиска, позволяющие эффективно решать поставленные перед ними задачи.
Поскольку при разработке современного программного обеспечения, особенно коммерческого назначения необходимо достаточно часто использовать сортировку большого объема значений для разного рода отчетов и т.п. то изучение имеющихся на данный момент реализаций алгоритмов сортировки является достаточно актуальным в данный момент.
Объект работы: алгоритмы используемые при разработке программного обеспечения.
Предмет работы: алгоритмы сортировки данных, используемые при разработке программного обеспечения.
Цель работы: изучение существующих алгоритмов сортировки, выяснения их особенностей и области применения каждого алгоритма, а также варианты их реализации на популярных языках программирования Basic, C, Delphi.
В ходе написания работы будет выявлена необходимость использования алгоритмов сортировки, область их применения, а также установлены разновидности методов сортировки. Помимо этого для каждого из методов сортировки будет установлен алгоритм, запись на популярных языках высокого уровня а также области применения данных алгоритмов и их особенности, влияющие на производительность разрабатываемого программного обеспечения.
В ходе написания работы использовалась литература по алгоритмам, основам программирования а также информация по языкам программирования С, Basic, Delphi.
1. Понятие сортировки, простые методы сортировки.
1.1. Понятие и обзор методов сортировки.
Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если
i <= i <= ... <= i
Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах.
Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.
В общем случае при сортировке данных только часть информации используется в качестве ключа сортировки, который используется в сравнениях. Когда выполняется обмен, передается вся структура данных. Например, в списке почтовых отправлений в качестве ключа сортировки может использоваться почтовый индекс, а в операциях обмена к почтовому индексу добавляются полное имя и адрес. Для простоты в примерах, иллюстрирующих методы сортировки, используются символьные массивы. Затем будет показано, как эти методы можно адаптировать к любым структурам данных.
Классы алгоритмов сортировки
Имеется три способа сортировки массивов: