Similar presentations:
Сортировки 1 курс плюс алг.слож
1. Квадратичные и эффективные сортировки
2. Алгоритмическая сложность
23. Оценка производительности алгоритмов
Для оценки производительности алгоритмовможно использовать разные подходы.
Самый бесхитростный - просто запустить
каждый алгоритм на нескольких задачах и
сравнить время исполнения.
Другой способ - оценить время исполнения
через символ 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/Snyn7EqHJMEhttps://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. Пример распределяющей (=сортировка подсчетом)
2021. Сортировка слиянием
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/