Алгоритмы и структуры данных на языке С

1.

Алгоритмы и
структуры данных на
языке С
Быстрая сортировка. Улучшения

2.

Быстрая сортировка.
Улучшения.

3.

1. "Толстое" разбиение
В этом видео
2. Улучшенная быстрая
сортировка
3. Плюсы и минусы быстрой
сортировки

4.

“Толстое” разбиение

5.

“Толстое” разбиение
равен
l
меньше
p
больше
i
j
равен
q
v
r

6.

“Толстое”
разбиение

7.

Улучшенная быстрая сортировка

8.

Улучшенная сортировка

9.

Плюсы и минусы быстрой сортировки

10.

Плюсы и минусы быстрой сортировки
Один из самых быстродействующих алгоритмов внутренней
сортировки общего назначения.
Для наилучшего случая
Ω(n log n);
Для среднего случая
θ(n log n);
Для худшего случая
O(n2);
Возможно переполнение стека;
Неустойчив.

11.

Рассмотрели:
Итоги
● "Толстое" разбиение
● Улучшенную быструю сортировку
● Плюсы и минусы быстрой сортировки