Файл: Алгоритмы сортировки данных (Теоретические основы алгоритмов сортировки данных).pdf

Алгоритм Шелла обладает следующими свойствами:

- Вычислительная сложность в среднем равна O(N3/2)). Если данные уже отсортированы, то необходимо сделать всего O(N*lgN) операций;

- Не требует использования дополнительной памяти (O(1));

- Неустойчив.

2.5. Сортировка слиянием

Данный алгоритм сортировки эффективен для структур с последовательным доступом. Идея алгоритма состоит в поэлементном слиянии двух отсортированных последовательностей. Эти последовательности могут получаться путём рекурсивного вызова. Такой подход реализован в примере.

Рисунок 9. Алгоритм сортировки слиянием

Рисунок 10. Листинг алгоритма сортировки слиянием

Сортировка слиянием обладает следующими свойствами:

- Вычислительная сложность в среднем равна O(N*lgN);

- Требует использования дополнительной памяти для слияния последовательностей (O(N));

- Устойчива.

2.6. Пирамидальная сортировка

Этот алгоритм сортировки использует специальную структуру данных – сортирующее дерево. Глубина листов такого дерева отличается не больше чем на 1, а значение в любой вершине не меньше значения потомков. На первом этапе пирамидальная сортировка создаёт такое дерево, а на втором последовательно удаляет из него корень и заново перестраивает [4, с. 311].

Рисунок 11. Алгоритм пирамидальной сортировки

Рисунок 12. Листинг алгоритма пирамидальной сортировки

Пирамидальная сортировка обладает следующими свойствами:

- Вычислительная сложность в среднем равна O(N*lgN);

- Не требует использования дополнительной памяти (O(1));

- Неустойчива;

- Сложна в реализации.

2.7. Быстрая сортировка

Общая идея алгоритма состоит в разделении входного набора данных относительно опорного элемента, выбираемого случайным образом. Все элементы, которые меньше опорного перемещаются в нижнюю часть массива, большие остаются на своих местах. В результате выполнения этих действий весь массива должен разделиться на три группы, следующие друг за другом: меньше опорного, равная опорному и больше опорного. Для «больших» и «меньших» отрезков рекурсивно выполняется та же последовательность действий. Для реализации данного алгоритма дополнительно приведена функция RandRange, дающая псевдослучайные числа в требуемом диапазоне.

Рисунок 13. Алгоритм быстрой сортировки

Рисунок 14. Листинг алгоритма быстрой сортировки

Быстрая сортировка обладает следующими свойствами:

- Вычислительная сложность в среднем равна O(N*lg(N)), в худших случая, при большом количестве неуникальных ключей может доходить до O(N2);

- Требует использования дополнительной памяти (в среднем O(lgN), в худшем O(N));

- Неустойчива.

Заключение

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

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

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

- сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены.

Существует огромное множество различных алгоритмов сортировки, и не всегда один определенный алгоритм может подойти к той или иной задаче. Именно поэтому так важно правильно понять, что и как делает алгоритм.

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

   1. Сортировка вставками. На каждом шаге алгоритма выбирается один из входящих элементов и вставляется на нужную позицию в уже отсортированной части массива, алгоритм выполняется до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

2. Сортировка выбором. Идея алгоритма заключается в нахождении на каждой итерации минимального элемента и перемещение его на нужную позицию в уже отсортированном массиве.

3. Сортировка пузырьком. Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. Алгоритм имеет такое название из-за того, что на каждой итерации наименьший элемент (самый лёгкий) «всплывает» до своей позиции.

4. Сортировка Шелла. Сортировка Шелла является усовершенствованным вариантом сортировки вставками. Идея данного метода состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Имеется большое количество модификаций, отличающихся выбором шага расстояния для каждой итерации.

5. Сортировка слиянием. Данный алгоритм сортировки эффективен для структур с последовательным доступом. Идея алгоритма состоит в поэлементном слиянии двух отсортированных последовательностей. Эти последовательности могут получаться путём рекурсивного вызова.

6. Пирамидальная сортировка. Этот алгоритм сортировки использует специальную структуру данных – сортирующее дерево. Глубина листов такого дерева отличается не больше чем на 1, а значение в любой вершине не меньше значения потомков. На первом этапе пирамидальная сортировка создаёт такое дерево, а на втором последовательно удаляет из него корень и заново перестраивает.

7. Быстрая сортировка. Общая идея алгоритма состоит в разделении входного набора данных относительно опорного элемента, выбираемого случайным образом. Все элементы, которые меньше опорного перемещаются в нижнюю часть массива, большие остаются на своих местах. В результате выполнения этих действий весь массива должен разделиться на три группы, следующие друг за другом: меньше опорного, равная опорному и больше опорного. Для «больших» и «меньших» отрезков рекурсивно выполняется та же последовательность действий.

Список использованной литературы

1. Бахвалов Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.Г Кобельков. – М.: Лаборатория Базовых Знаний, 2017. – 241 с.
2. Вирт Н. Алгоритмы и структуры данных: в 2 книгах / Н. Вирт – СПб.: Невский диалект, 2016. – Кн. 1. – 410 с.
3. Голицына О.Л. Основы алгоритмизации и программирования / О.Л. Голицина, И.И. Попов. – М.: ИНФРА-М, 2017. – 432 с.
4. Давыдов В.Г. Программирование и основы алгоритмизации / В.Г. Давыдов. – М.: Высшая школа, 2017. – 447 с.
5. Динман М.И. C++. Освой на примерах. – СПб.: БХВ-Петербург, 2017. – 384 с.
6. Емельянов В.И. Основы программирования на Delphi / В.И. Емельянов, В.И. Воробьев, Т.П. Тюрина. – М.: Высшая школа, 2016. – 232 с.
7. Желонкин А. Основы программирования в интегрированной среде Delphi / А. Желонкин, – М.: БИНОМ. Лаборатория знаний, 2016. – 240 с.
8. Зуев Е. А., Чупринов А. А. Стандарт С++: перевод, комментарии, примеры. М.: ООО «Ваш формат», 2016. - 888 с.
9. Кнут Д.Э. Искусство программирования: Пер.с англ.: В 3-х т. Т.3: Сортировка и поиск / Д. Э. Кнут. - М.: Вильямс, 2017. – 832 с.
10. Кормен Т. Алгоритмы. Вводный курс / Т. Кормен. – М.: МЦНМО, 2017. – 264 с.
11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Т. Кормен – М.: Центр непрер. матем. образ-я, 2017. – 960 с.
12. Культин Н. Основы программирования в Delphi 7 / Н. Культин. – СПб.: БХВ-Петербург, 2017. — 896 с.
13. Левитин А. Алгоритмы. Введение в разработку и анализ / А. Левитин. - М.: Вильямс, 2017. – 562 с.
14. Липачев Е.К. Технология программирования. Базовые конструкции языка C/C++. – Казань: Казанский университет, 2017. – 142 с.
15. Лэнгсам Й. Структуры данных для персональных ЭВМ / Й. Лэнгсам, М. Огенстайн, А. Тененбаум. - М.: Мир, 2015. - 366 с.
16. Макконелл Дж. Основы современных алгоритмов. - М.: Техносфера, 2017. - 368 с.
17. Михеева Е.В. Практикум по информационным технологиям в профессиональной деятельности: Учеб. пособие / Е.В. Михеева. - М.: Академия, 2017. – 256 с.
18. Незнанов А. А. Программирование и алгоритмизация / А.А. Незнанов. – М.: Академия, 2016. – 304 с.
19. Павловская Т.А. Программирование на языке высокого уровня / Т.А. Павловская. – СПб.: Питер, 2016. – 461 с.
20. Прата С. Язык программирования C++. Лекции и упражнения. – М.: Вильямс, 2017. – 1248 с.
21. Седжвик Р. Алгоритмы на С++. Фундаментальные алгоритмы и структуры данных / пер. с англ. (Algorithms in C++). - М.: Вильямс, 2017. - 1056 с.
22. Сибуя М. Алгоритмы обработки данных / М. Сибуя, Т. Ямамото, – М.: Мир, 2015. – 308 с.
23. Сухарев М.В. Основы Delphi. Профессиональный подход / М.В. Сухарев. – СПб.: Наука и техника, 2016. – 420 с.
24. Угринович Н.Д. Исследование информационных моделей. Элективный курс / Н.Д. Угринович. – М.: БИНОМ. Лаборатория знаний, 2017. – 183 с.
25. Фридман А., Кландер Л., Михаэлис М., Шильдт Х. C/C++. Архив программ. – М.: БИНОМ, 2017. – 640 с.
26. Хэзфилд Р., Кирби Л. И др. Искусство программирования на C. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста. – К.: ДиаСофт, 2016. – 736 с.
27. Чеснокова О.В. Delphi 2007. Алгоритмы и программы / О.В. Чеснокова. – М.: БИНОМ; Лаборатория знаний, 2016. – 368 с.
28. Шилдт Г. Полный справочник по C: Пер.с англ. / Г. Шилдт. - М.: Вильямс, 2016. – 278 с.