Page 86 - Bkhargava_-_Grokaem_algoritmy

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

Упражнения

4.1 Напишите код для функции sum (см. выше).

4.2 Напишите рекурсивную функцию для подсчета
элементов в списке.
4.3 Найдите наибольшее число в списке.

4.4 Помните бинарный поиск из главы 1? Он тоже
относится к классу алгоритмов •разделяй и властвуй•. Сможете ли вы
определить базовый и рекурсивный случай для бинарного поиска?

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

Быстрая сортировка относится к алгоритмам сортиров­
ки. Она работает намного быстрее сортировки выбором
и часто применяется в реальных программах. Например,
в стандартную библиотеку С входит функция с име­
нем qsort, реализующая быструю сортировку. Быстрая
сортировка также основана на стратегии ~разделяй
и властвуй•.

Воспользуемся быстрой сортировкой для упорядо­
чения массива. Как выглядит самый простой массив,
с которым может справиться алгоритм сортировки
(помните подсказку из предыдущего раздела)? Не­
которые массивы вообще не нуждаются в сорти­
ровке.

[ ] ~ ПУСТО~ MACCll&
СОРТМРО&АТЬ
ПКМЕ MACCll&bl
( 20 \ ~ MKCll& С OJUlllM ЭЛЕМЕНТОМ
НЕ нv.~но

www.trk.kg