Квадратичные и эффективные сортировки
Алгоритмическая сложность
Оценка производительности алгоритмов
Что означает символ O(n) ?
Что означает символ O(n) ?
Про O(n) видео от Сириуса
Квадратичные алгоритмы сортировки
Некоторые сортировки
Сортировка выбором
Сортировка выбором
Сортировка пузырьком
Сортировка пузырьком
Сортировка вставками
Cортировка вставками
Быстрая сортировка
Сравнение времени квадратичных сортировок
Эффективные сортировки
Распределяющая сортировка: Для массивов
Распределяющая сортировка: Для списков
Пример распределяющей (=сортировка подсчетом)
Сортировка слиянием
Сортировка слиянием
Сравнение разных сортировок
Охарактеризуем сортировки по четырем параметрам:
Распределяющая сортировка: Для массивов
Распределяющая сортировка: Для списков
Сортировка двоичным деревом
Quicksort - быстрая сортировка
Heapsort - пирамидальная сортировка
Mergesort - сортировка слиянием
Рекомендации по выбору сортировки
Создание большого набора данных
Предварительная работа
Основная работа
Результаты проверки
Литература
1.34M
Category: programmingprogramming

Сортировки 1 курс плюс алг.слож

1. Квадратичные и эффективные сортировки

2. Алгоритмическая сложность

2

3. Оценка производительности алгоритмов

Для оценки производительности алгоритмов
можно использовать разные подходы.
Самый бесхитростный - просто запустить
каждый алгоритм на нескольких задачах и
сравнить время исполнения.
Другой способ - оценить время исполнения
через символ O(n)
3

4. Что означает символ O(n) ?

Оценки времени исполнения
4

5. Что означает символ O(n) ?

Если оба алгоритма, например, O ( n*log n ), то это отнюдь
не значит, что они одинаково эффективны.
Символ О не учитывает константу, то есть первый может
быть, скажем в 1000 раз эффективнее. Это значит лишь
то, что время (или требуемая память или что-либо еще,
что надо оценить) возрастает приблизительно c такой же
скоростью, как функция n*log n
Если в программе одна функция выполняется O(n) раз например, умножение, а сложение - O(n^2) раз, то общая
сложность - O(n^2), так как n^2 возрастает быстрее.
5

6. Про O(n) видео от Сириуса

https://youtu.be/Snyn7EqHJME
https://youtu.be/5P-I6RSQGtY (логарифм)
6

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

Список, примеры, время
выполнения

8. Некоторые сортировки

Пирамидальная
Быстрая
Пирамидальная
Слиянием
Пузырьком + модификации
Вставками
Шелла
Выбором
Топологическая
Быстрая с составными ключами

9. Сортировка выбором

Находим наибольший элемент в массиве и
ставим его на первое место, затем находим
наибольший элемент из оставшихся и
ставим его на второе место и т.д. Таким
образом, в решении имеется циклfor(i = 0; i
< n -1; ++i), внутри которого находится
наибольший элемент средиA[i],A[i+1],
...,A[n-1], который устанавливается на
местоA[i].
9

10. Сортировка выбором

11. Сортировка пузырьком

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

12. Сортировка пузырьком

13. Сортировка вставками

В каждый произвольный момент начальная
часть массива уже отсортирована. В
решении имеется цикл for(i = 1; i < n; ++i),
внутри которого в предположении, что
элементы массива A[0],A[1], ...,A[i-1]уже
отсортированы, элемент A[i]добавляется в
отсортированную часть. Для этого
находится позиция, в которую необходимо
вставить элемент A[i], затем
осуществляется циклический сдвиг
фрагмента уже отсортированной части.
13

14. Cортировка вставками

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

Выберем случайным образом какой-то элемент х и
просмотрим массив, двигаясь слева направо, пока не найдем
аi больший x, а затем справа налево, пока не найдем аi
меньший х. Поменяем их местами и продолжим процесс
просмотра с обменом, пока просмотры не встретятся где-то в
середине массива. В результате массив разделится на две
части: левую - с ключами, меньшими х и правую - с ключами,
большими х. Этот шаг называется разделением. Х - центром.
К получившимся частям рекурсивно применяем ту же
процедуру. В результате получается очень эффективная
сортировка.
Среднее быстродействие O(nlogn), но возможен случай таких
входных данных, на которых алгоритм будет работать за
O(n^2) операций.
15

16. Сравнение времени квадратичных сортировок

Коричневая: сортировка
пузырьком
синяя: шейкер-сортировка;
розовая: сортировка
выбором
желтая: сортировка
вставками
голубая: сортировка
вставками со сторожевым
элементом
фиолетовая: сортировка
Шелла

17. Эффективные сортировки

18. Распределяющая сортировка: Для массивов

1.
2.
3.
4.
Общее быстродействие O(k(n+s)) [s
иногда не учитывают вовсе]
Реализация со временным массивом
O(n), [Radix Sort] Реализация без
временного массива O(logn) [Radix
Exchange Sort]
Реализация со временным массивом
устойчивая, Реализация без временного
массива неустойчивая.
Hеестественное поведение
18

19. Распределяющая сортировка: Для списков

1.
2.
3.
4.
Общее быстродействие O(k(n+s)) [s
иногда не учитывают]
Дополнительной памяти не требуется,
так как реорганизовывать список можно
просто через указатели
Устойчивая сортировка
Hеестественное поведение
19

20. Пример распределяющей (=сортировка подсчетом)

20

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

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

23. Сравнение разных сортировок

Сравнение по 4 параметрам

24. Охарактеризуем сортировки по четырем параметрам:

1.
Время сортировки
2.
Память - дополнительные затраты памяти,
зависящие от размера массива.
3.
Устойчивость - устойчивая сортировка не
меняет взаимного расположения равных
элементов
4.
Естественность поведения - эффективность
метода при обработке уже отсортированных,
или частично отсортированных данных

25. Распределяющая сортировка: Для массивов

1.
Общее быстродействие O(k(n+s))
2.
Реализация со временным массивом
O(n), реализация без временного
массива O(logn)
3.
Реализация со временным массивом
устойчивая, без него неустойчивая
4.
Hеестественное поведение

26. Распределяющая сортировка: Для списков

1.
Общее быстродействие O(k(n+s))
2.
Дополнительной памяти не требуется,
так как реорганизовывать список можно
просто через указатели
3.
Устойчивая сортировка
4.
Hеестественное поведение

27. Сортировка двоичным деревом

1.
Общее быстродействие O(nlogn)
2.
Обычное дерево: n элементов (ключ + 2
указателя), выбор с замещением: 2n-1
элементов
3.
Устойчивости нет
4.
Поведение неестественно

28. Quicksort - быстрая сортировка

1.
Общее быстродействие O(nlogn)
2.
Итерационный вариант требует log n
памяти, рекурсивный - O(n)
3.
Устойчивости нет
4.
Поведение неестественно

29. Heapsort - пирамидальная сортировка

1.
Общее быстродействие всегда O(nlogn)
2.
Сортировка 'на месте'
3.
Устойчивости нет
4.
Поведение неестественно

30. Mergesort - сортировка слиянием

1.
Общее быстродействие - O(nlogn)
2.
O(n)
3.
Устойчивая
4.
Hа практике используются реализации с
естественным поведением

31. Рекомендации по выбору сортировки

Малые массивы/списки - менее 20
элементов => InsertSort
Большие массивы => QuickSort,
Heapsort
Длинные списки/файлы => MergeSort
Если количество возможных различных
ключей ненамного больше их общего
числа - то наибыстрейшей будет
распределяющая сортировка

32. Создание большого набора данных

33. Предварительная работа

Сгенерировать в цикле
набор случайных чисел.
Количество 108, диапазон
0-106
Сохранить в файл
1 Гб информации

34. Основная работа

Реализовать в коде на выбор 2
сортировки:
Пузырьком или вставками
MergeSort или QuickSort или
Пирамидальная
Применить, засечь время исполнения
Записать упорядоченный набор в новые
файлы

35. Результаты проверки

Время исполнения на 108, диапазон 0-106
пузырьком 7-8 секунд
QuickSort менее 1 секунды
O(n2)
Распределяющая сортировка? O(n)
MergeSort? O(n*logn)
Пирамидальная?

36. Литература

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.
Алгоритмы: построение и анализ, 2-е
издание.стр. 110 М.: Издательский дом
"Вильямс", 2005. ISBN 5-8459-0857-4
Кнут Д. Искусство программирования. — 3-е изд.
— М.: Вильямс, 2007. — Т. 2. Получисленные
алгоритмы. — 832 с. — ISBN 0-201-89684-2.
https://neerc.ifmo.ru/wiki/index.php?title=Мастертеорема
http://algolist.ru/olimp/sor_prb.php
https://habr.com/ru/post/281675/
English     Русский Rules