Эффективные алгоритмы сортировки

1. Эффективные алгоритмы сортировки

ВЫПОЛНИЛ: УЧЕНИК 11 «В» КЛАССА
МОУ ГИМНАЗИИ ИМ. А. Л. КЕКИНА
ХАИРНУРОВ ТИМУР
РУКОВОДИТЕЛЬ: УЧИТЕЛЬ ИНФОРМАТИКИ САМАРЧЕНКО Н. В.

2. Цель работы

Рассмотреть различные алгоритмы сортировки, сравнить их и выяснить, какой из
них будет работать эффективнее в различных условиях

3. Задачи

1. Определить, что такое алгоритмы сортировки
2. Изучить как работают алгоритмы сортировки
3. Рассмотреть различные алгоритмы
4. Выявить критерии оценки эффективности

4. Что такое алгоритмы сортировки?

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

5. Принцип работы алгоритмов сортировки

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

6. Принцип работы алгоритмов сортировки

7. Критерии оценки алгоритмов сортировки

Время сортировки - основной параметр, характеризующий быстродействие
алгоритма. Называется также вычислительной сложностью.
Память. Ряд алгоритмов требует выделения дополнительной памяти под
временное хранение данных. При оценке используемой памяти не будет
учитываться место, которое занимает исходный массив и независящие от входной
последовательности затраты, например, на хранение кода программы.

8. Критерии оценки алгоритмов сортировки

Устойчивость. Устойчивая сортировка не меняет взаимного расположения равных
элементов. Такое свойство может быть очень полезным, если они состоят из
нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже
отсортированных, или частично отсортированных данных. Алгоритм ведёт себя
естественно, если учитывает эту характеристику входной последовательности и
работает лучше.

9. Сортировка пузырьком (Bubble sort)

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

10. Сортировка пузырьком (Bubble sort)

11. Сортировка вставками (Insertion sort)

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

12. Сортировка вставками (Insertion sort)

13. Сортировка Шелла (Shell Sort)

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

14. Сортировка Шелла (Shell Sort)

15. Быстрая сортировка (Quick Sort)

Этот широко известный алгоритм сортировки был разработан английским информатиком
Чарльзом Хоаром во время его работы в МГУ в советские годы. Из-за наличия ряда
недостатков на практике обычно используется с некоторыми доработками.
Он основан на использовании обменного метода сортировки. Это тем более удивительно,
если учесть очень низкое быстродействие сортировки пузырьковым методом, который
представляет собой простейшую версию обменной сортировки
Если выбираемое для разбиения значение оказывается совпадающим с максимальным
значением, то быстрая сортировка превращается в самую медленную с временем
выполнения n. Быстрая сортировка относится к алгоритмам «разделяй и властвуй».

16. Быстрая сортировка (Quick Sort)

Алгоритм состоит из трёх шагов:
1. Выбор опорного элемента из массива.
2. Перераспределение элементов в массиве таким образом, что элементы меньше
опорного помещаются перед ним, а больше или равные — после.
3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от
опорного элемента. Рекурсия не применяется к массиву, в котором только один или
отсутствуют элементы.

17. Быстрая сортировка (Quick Sort)

18. Сравнение алгоритмов сортировки

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

19. Сравнение алгоритмов сортировки

Сортировка пузырьком
№
Время, мс
I группа
Сортировка вставками
№
II группа
Время, мс
I группа
Сортировка Шелла
№
II группа
Быстрая сортировка
Время, мс
I группа
№
II группа
Время, мс
I группа
II группа
1
1973
3060854
1
522
2709423
1
2
356
1
55
14515
2
1967
3220258
2
612
2718324
2
1
357
2
117
16501
3
2065
3199684
3
418
2719348
3
0
340
3
65
16912
4
1954
3175024
4
444
2729185
4
1
344
4
74
14420
5
1948
3168734
5
432
2719567
5
0
347
5
62
16240
6
1982
3158682
6
405
2729651
6
2
343
6
65
16092
7
1993
3166572
7
414
2723096
7
2
365
7
81
13958
8
2041
3173164
8
422
2715904
8
1
350
8
124
14866
9
2169
3195290
9
426
2725603
9
0
348
9
107
16292
10
1961
3160696
10
419
2713495
10
0
355
10
76
16097

20. Сравнение алгоритмов сортировки

Результаты получились интересными. Для обеих групп тестов самым быстрым алгоритмом
оказалась не Быстрая Сортировка, а метод Шелла. Затем идут Сортировка вставками и
Метод пузырька.
I группа
II группа
Среднее время, мс
Среднее время, мс
Сортировка Шелла
Быстрая Сортировка
Сортировка
Вставками
Метод Пузырька
0,9
82,6
451,4
2005,3
Сортировка Шелла
Быстрая Сортировка
350,5
15589,3
Сортировка
Вставками
2720359,6
Метод Пузырька
3167895,8

21. Заключение

Подведем итоги. Я узнал, что такое алгоритмы сортировки, изучил принцип
их работы и сравнил данные алгоритмы сортировки, и для выбранных
мною тестов самым быстрым алгоритмом оказалась Сортировка Шелла.
Для решения задач ЕГЭ, я бы посоветовал использовать либо её, либо
быструю сортировку.

22. Источники

Опанасенко М. Описание алгоритмов сортировки и сравнение их производительности:
[Электронный ресурс]. URL: https://habr.com/ru/post/335920/ (Дата обращения: 20.10.2021)
Е. Туренко Визуализации алгоритмов сортировки: [Электронный ресурс]. URL:
https://tproger.ru/digest/sorting-algorithms-visualized/ (Дата обращения: 23.10.2021)
Курсовая работа: Алгоритмы сортировки: [Электронный ресурс]. // Липецк 2011 URL:
https://studrb.ru/works/entry9551 (Дата обращения: 24.10.2021)
Сортировка Шелла: [Электронный ресурс]. URL:
https://ru.wikipedia.org/wiki/Сортировка_Шелла (Дата обращения: 24.10.2021)
Быстрая сортировка: [Электронный ресурс]. URL:
https://ru.wikipedia.org/wiki/Быстрая_сортировка (Дата обращения: 24.10.2021)