2.5.2 Описание

Быстрая сортировка (quicksort), как и сортировка слиянием, основана на принципе «разделяй и властвуй». Сортировка участка A[p..r] происходит следующим образом.

• Элементы массива А переставляются так, чтобы любой из элементов А[p],...,A[q] был не больше любого из элементов A[q + 1],..., А[r], где q – некоторое число в интервале р ≤ q < r. Эта операция называется разделением (partition).

• Процедура сортировки рекурсивно вызывается для массивов A[р..q] и A[q + 1..r].

После этого массив A[р..r] отсортирован.

Листинг 2.6 – Процедура быстрой сортировки