Similar presentations:
Эффективные алгоритмы сортировки
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)