Бинарный поиск

1.

Бинарный поиск
Цель. Найти индекс ключа в отсортированном
массиве
Бинарный поиск
Ключ меньше — идем влево
Ключ больше — идем вправо
Равен — возвращаем результат

2.

Сортировка выбором
На итерации i найти минимальный оставшийся
элемент с индексом min
Поменять местами a[i] и a[min]
Видео 1

3.

Сортировка выбором
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы и не
меняются
Нет элемента справа от стрелки, который был бы
меньше элемента слева от стрелки

4.

Сортировка выбором: внутренний цикл

5.

Сортировка выбором: реализация на Java

6.

Сортировка выбором:
математический анализ
Утверждение. Сортировка выбором использует (N1) + (N-2) + … + 1 + 0 ~ N2/2 сравнений и N
перестановок
Время выполнения не зависит от входных данных.
Квадратичное время, даже если массив

7.

Видео 2

8.

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

9.

Сортировка вставками
На итерации i поменять a[i] с каждым большим
элементом слева
Видео 3

10.

Сортировка вставками
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы по
возрастанию
Элементы справа от стрелки еще не проверены

11.

Сортировка вставками: внутренний цикл

12.

Сортировка вставками: реализация на Java

13.

Сортировка вставками:
математический анализ
Утверждение. Сортировка вставками использует ~
N2/4 сравнений и ~ N2/4 перестановок при
случайном наборе данных
В среднем каждый ключ проходит половину пути

14.

Сортировка вставками: пример

15.

Видео 4

16.

Сортировка вставками: лучший и
худший случай
Лучший случай. Массив отсортирован; необходимо
N-1 сравнений и 0 перестановок
AEELMOPRSTX
Худший случай. Массив отсортирован в обратно
порядке и нет дубликатов; ~ N2/2 сравнений и ~
N2/2 вставок
XTS R PO M LE EA

17.

Видео 5

18.

Сортировка вставками: частично
упорядоченный массив
Инверсия — пара элементов, которая нарушает
упорядоченность в массиве
Частично упорядоченный массив — массив, в
котором количество инверсий <= cN
Массив, каждый элемент которого находится
неподалеку от своей окончательной позиции
Небольшой массив, добавленный к большому
отсортированному массиву

19.

Видео 6