Алгоритмы сортировки и поиска презентация

Лекция 1.2 Алгоритмы сортировки и поиска

Можно ли еще улучшить алгоритм поиска?

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

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

Алгоритм бинарного поиска

Рекурсивный вариант бинарного поиска

Время работы бинарного поиска

Сортировка

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

Алгоритм сортировки выбором

Алгоритм сортировки выбором

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

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

Алгоритм сортировки вставкой

Время работы сортировки вставкой

Время работы сортировки вставкой

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

Алгоритм сортировки слиянием

Пример: Merge-Sort(A,1,10)

Процедура слияния

Алгоритм слияния подмассивов

Время работы сортировки слиянием

Сравнение алгоритмов сортировки

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

Процедура быстрой сортировки

Процедура разбиения

Процедура разбиения

Время работы быстрой сортировки

Время работы быстрой сортировки

Резюме

Можно ли превзойти время сортировки Θ(nlog2n)?

Простая сортировка за время Θ(n)

Процедура очень простой сортировки

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

1) Вычислим, у какого количества элементов ключи сортировки равны заданному значению

2) Выясним, у какого количества элементов ключи сортировки меньше каждого возможного значения

3) Создадим отсортированный массив путем перемещения элементов из массива А в массив В так, чтобы они в конечном итоге оказались в массиве В в отсортированном порядке

4) Собираем все три процедуры вместе для создания окончательной процедуры сортировки подсчетом

Время работы сортировки подсчетом

Устойчивость сортировки

Поразрядная сортировка

Пример поразрядной сортировки

Время работы поразрядной сортировки