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

Быстрая сортировка — это алгоритм сортировки, время работы которого для входного массива из nчисел в наихудшем случае равноO(п²). Несмотря на такую медленную работу в наихудшем случае, этот алгоритм на практике зачастую ока­зывается оптимальным благодаря тому, что в среднем время его работы намного лучше:O(nlgn). Кроме того, постоянные множители, не учтенные в выражении 0(nlgn), достаточно малы по величине. Алгоритм обладает также тем преиму­ществом, что сортировка в нем выполняется без использования дополнительной памяти, поэтому он хорошо работает даже в средах с виртуальной памятью.

Принцип работы метода.

Быстрая сортировка, подобно сортировке слиянием, основана на парадигме "разделяй и властвуй". Ниже описан процесс сортировки подмассива А [p,..r], состоящий, как и все алгоритмы с использованием декомпозиции, из трех этапов.

Разделение. МассивА[p..r] разбивается (путем переупорядочения его элемен­тов) на два (возможно, пустых) подмассиваA [p..q-1]и A[q+1..r]. Каж­дый элемент подмассива

A [p..q-1] не превышает элементA[q], а каждый элемент подмассива[q+1..r] не меньше элементаA[q]. Индексq вычис­ляется в ходе процедуры разбиения.

Покорение. ПодмассивыA [p..q-1] иA[q+1..r] сортируются путем рекурсив­ного вызова процедуры быстрой сортировки.

Комбинирование. Поскольку подмассивы сортируются на месте, для их объеди­нения не нужны никакие действия: весь массивА [р..г] оказывается отсор­тирован.

Алгоритм сортировки реализуется представленной ниже процедурой:

Quicksort (A, p, r)

1 if р < r

2 then q Partition (A, p, r)

3. Quicksort (A, p,q- 1}

4. Quicksort (A, q + 1, r)

Чтобы выполнить сортировку всего массива А, вызов процедуры должен иметь видQuicksort(A, 1, lehgth [A]).

Ключевой частью рассматриваемого алгоритма сортировки является процеду­ра PARTITION, изменяющая порядок элементов подмассива А [p..r] без привлечения дополнительной памяти:

Partitionist(A,p, r )

1. хА[r]

2. iр-1

3. for j р to r - 1

4 doifA[j] x

5 then i i + 1

6 Обменять А[i] A[j]

7. Обменять A[i + 1] A [r]

8. return i + 1

Производительность быстрой сортировки хорошо изучена. Алгоритм подвергался математическому анализу, поэтому существуют точные математические формулы касающиеся вопросов его производительности. Результаты анализа были неоднократно проверены эмпирическим путем, и алгоритм был отработан до такого состояния, что стал наиболее предпочтительным для широкого спектра задач сортировки. Все это делает алгоритм стоящим более детального изучения наиболее эффективных путей его реализации. Похожие способы реализации подходят также и для других алгоритмов, но в алгоритме быстрой сортировки мы можем использовать их с уверенностью, поскольку его производительность хорошо изучена.

5.3. Теоретические аспекты определения времени выполнения сортировок

Говорят, что функция f(n)=O(g(n) ("f(n) есть O-большое от g(n)"), если существует такая константа C, что |f(n)|<C|g(n)|, для всех n>n₀. Или так

В этом случае также говорят, что f(n) растет не быстрее, чем g(n). Например, 2*n³+ 3n + 1/n = O(n³); n = O(n²). Еще один пример: n!=1*2*...*n = O(nⁿ).

Будем говорит, что f(n) растет медленнее, чем g(n), или f(n)=o(g(n)) ("о-малое"), если

Иногда это записывают так: f(n) ‹ g(n). Например, n ‹ n². Еще один пример: 1 ‹ lglg n ‹ lg n ‹ n^1/a ‹ n^a ‹ n^{lg a} ‹ aⁿ ‹ nⁿ, a>1.

Рис.5.5. Сравнение скорости роста функций. Наконец, будем говорить, что f(n) растет также как g(n), обозначают f(n)~g(n), если

это то же самое, что: f(n)=O(g(n)) и g(n)=O(f(n)). Например, 2*n³+ 3n + 1/n ~ n³. Еще один пример: log₂n ~ log_en ~ log₁₀~ log_an, a>0.

Поскольку для асимптотического оценивания не имеет значение по какому основанию берется логарифм, то в дальнейшем мы будем записывать просто log(n) или logn, без указания его основания.

Для оценивания сложности алгоритма используются функции из класса логарифмически-экспоненциальных функций. В некоторых случаях выделяют особые классы сложности:

1) логарифмическая сложность: O(log n), 2) линейная сложность: O(n), 3) квазилинейная сложность: О(nlog n), 4) квадратичная cложность: O(n²), 5) кубическая сложность: О(n³), 6) полиномиальная сложность: О(n^p), p - натуральное, 7) экспоненциальная сложность: О(2ⁿ), 8) О(nⁿ).