Перетасовка Кнута. Быстрая сортировка (Quicksort)

Сентябрь 7, 2022

Главная
Алгебра
Перетасовка Кнута. Быстрая сортировка (Quicksort)

Содержание

5. Быстрая сортировка (Quicksort)
6. Два классических алгоритма сортировки Критические компоненты в мировой вычислительной инфраструктуре Понимание научных основ этих алгоритмов даст
8. Быстрая сортировка Основной план Перемешать элементы случайным образом Разбиение для элемента j a[j] оставить на месте
9. Быстрая сортировка Повторять до тех пор, пока i и j не пересекутся Проверять i-ые элементы до
10. Быстрая сортировка: реализация разбиения на Java
11. Быстрая сортировка: реализация на Java
12. Быстрая сортировка
13. Быстрая сортировка
14. Быстрая сортировка: реализация Не требует дополнительной памяти Выход из циклов. Обращайте особое внимание на условия выхода
15. Быстрая сортировка: лучший случай Лучший случай. Количество сравнений ~ N log2N
16. Быстрая сортировка: худший случай Худший случай. Количество сравнений ~ ½ N2
18. Скачать презентацию

Слайд 2

Слайд 3

Слайд 4

Слайд 5

Быстрая сортировка
(Quicksort)

Слайд 6

Два классических алгоритма сортировки
Критические компоненты в мировой вычислительной инфраструктуре
Понимание научных основ

этих алгоритмов даст нам возможность разрабатывать прикладные системы для решения реальных задач
Быстрая сортировка входит в десятку самых полезных алгоритмов, разработанных в 20-м веке

Слайд 7

Слайд 8

Быстрая сортировка
Основной план
Перемешать элементы случайным образом
Разбиение для элемента j
a[j] оставить на

месте
Нет элементов меньше чем a[j] с правой стороны
Нет элементов больше чем a[j] с левой стороны
Отсортировать каждую часть рекурсивно

Слайд 9

Быстрая сортировка
Повторять до тех пор, пока i и j не пересекутся
Проверять

i-ые элементы до тех пор пока a[i] < a[lo]
Проверять j-ые элементы до тех пор пока a[j] > a[lo]
Поменять местами a[i] и a[j]
Видео 1

Слайд 10

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

Слайд 11

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

Слайд 12

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

Слайд 13

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

Слайд 14

Быстрая сортировка: реализация
Не требует дополнительной памяти
Выход из циклов. Обращайте особое внимание

на условия выхода из циклов
Ограничения. Проверка j == lo излишняя, но i == hi нет
Рандомизация. Перетасовка нужна чтобы обеспечить гарантии производительности
Равные ключи. Если присутствуют дубликаты, то можно использовать другой вариант алгоритма

Слайд 15