Алгоритмы

1.

Алгоритмы

2.

План
Сортировка
Сортировка парными перестановками
Сортировка пирамидой?
Быстрая сортировка
Оценка скорости алгоритма

3.

Сортировки
Мотивировка
Что такое сортировка?
Зачем сортировать данные?
Каковы преимущества работы с
сортированными данными?
Где применяются сортировки?

4.

Сортировка выбором: интуитивная
сортировка
Логика сортировки состоит в том, что бы искать минимальный
элемент и отделяется в отсортированную часть. Потом ищется
следующий минимальный элемент и т.д.

5.

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

6.

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

7.

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

8.

Сортировки вставками: анализ
Характеристики алгоритма:
Input size (размер входа) – количество
элементов массива, количество байт,
количество рёбер и вершин…
Running time (время работы) – количество
элементарных шагов.
Memory size – количество памяти
используемое для проведения сортировки

9.

Сортировка вставками: время работы

10.

Сортировка вставками: время работы
Время выполнения алгоритма зависит не
только от размера входных данных, но и от его
их упорядоченности.
Сортировка вставками имеет лучший случай,
когда массив уже отсортирован т.к. цикл на 5
строке будет завершаться после 1 итерации и
худший когда он отсортирован в обратной
последовательности.

11.

Сортировка вставками: время работы
Общий случай
Лучший случай

12.

Сортировка вставками: время
работы
Худший случай

13.

Оценка времени работы алгоритма
Для оценки алгоритма используют время работы
в худшем случае:
– Зная время работы в худшем случае мы можем
гарантировать время окончания работы независимо
от конкретного входа
– На практике стоит оценивать количество худших
случаев, но не забывать о том, что из-за разницы в
случае разница во времени может быть очень велика
– Время работы в среднем случае очень часто
стремится к времени работы в худшем случае

14.

Порядок роста времени работы
~
~

15.

Сортировка слиянием
Идея метода заключается на принципе «разделяй и властвуй». Другими
словами массив делится на два массива до тех пор, пока не будет разбит на
пары элементов(или 1 элемент, если количество элементов нечётное).
После чего элементы массивов попарно сравниваются и формируют
отсортированный массив двойной длины.
Цикл слияния выполняется до тех пор пока все части массива не будут
объединены в один массив, который будет отсортирован.

16.

Сортировка слиянием
Что
бы
отсортировать
Merge-sort(Arr,1, Arr.length)
весь
массив
необходимо
вызвать
метод

17.

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

18.

Оценка алгоритмов сортировок
Алгоритм
Время выполнения в худшем случае
Выбором
O(n^2)
Вставками
O(n^2)
Слиянием
O(nlogn)
Кучей или пирамидальная
O(nlogn)
Быстрая
O(n^2)
Бинарным деревом
O(nlogn)

19.

Задание на самостоятельную работу
Отсортировать массив
Вариант 1
Вариант 2
Вариант 3
Выбором
5,7,2,5,3,8
5,6,1,5,7,8,3,2
51,2,42,45,31,9,4,6
Вставками
15,27,22,51,32,81 15,27,3,2,1,28,2,1 23,7,72,6,3,4,21,9
Слиянием
5,7,2,5,3,8,2,1
51,2,3,6,8,9,3,1
6,8,1,4,3,9,3,7