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

Быстрая сортировка (или обменная сортировка с разделением)

Этот метод основан на сравнениях ключей и обменах пар элементов, расположенных не в соседних позициях , а удалённых друг от друга в сортируемом массиве.

Быстрая сортировка позволяет сократить количество необходимых операций от величины O(n²) в среднем до величины O(n*log₂(n)). Но в худшем случае, если сортируются данные … то быстрая сортировка имеет O(n²).

В основе быстрой сортировки лежит процедура разделения сортируемого массива на две части следующим образом:

A = (a₁, a₂, …, a_n) –сортируемый массив

Для его разделения на две части выбирается некоторый элемент x данного массива, называемый разделяющий элемент.

Пусть x = a₁.

После выбора x элементы массива переупорядочиваются следующим образом

1. Разделяющий элемент размещается в некоторой позиции j: a_j := x.

2. Все элементы первой части массива A₁ = (a₁, a₂, …, a_j-1) должны удовлетворять условию

f(a_i)≤f(a_j), i = 1, 2, .., j-1.

3. Все элементы второй части массива A₂ = (a_j+1, a_j+2, …, a_n) должны удовлетворять условию

f(a_j)≤f(a_i), i = j+1, j+2, .., n.

Если такое разделение выполнено, то исходный массив A можно представить следующим образом:

A = (a₁, a₂, …, a_j-1) a_j (a_j+1, a_j+2, …, a_n).

В этом массиве разделяющий элемент занимает такое место, в котором он должен находиться после полного упорядочивания. Далее чтобы построить алгоритм сортировки в целом нужно рекуррентно повторить процедуру разделения для вновь полученных массивов A₁ и A₂, а также для всех подмассивов, созданных при последнем разделении.

Рассмотрим процедуру разделения подробно.

Пусть A – исходный неупорядоченный массив. Введём два счётчика: i = 1, j = n для просмотра элементов слева и справа. Примем в качестве разделяющего x = a_i.

1. Просматриваются элементы массива справа и их ключи сравниваются с ключами разделяющего элемента.

Если f(aj)≤f(ai), то выбирается следующий элемент, т.е. j = j – 1. иначе производится обмен местами элементов a_i и a_j; переменная i увеличивается на единицу i = i + 1; x=a_j .

2. Выполняется аналогично, но просматриваются элементы массива слева и их ключи сравниваются с ключами разделяющего элемента.

3. Шаги 1 и 2 повторяются до тех пор, пока после некоторого из них не будет получено равенство значений i = j. Это означает что разделение закончено и разделяющий элемент находится в позиции i = j, x = a_i = a_j.

Покажем на примере по шагам.

Исходный массив: (25, 57, 48, 37, 12, 92, 86, 33).

Шаг	Элементы								Действие
0	25	57	48	37	12	92	86	33	i = 1, j = 8, x = a1
1	25							33	j = j – 1 = 7
2	25						86		j = j – 1 = 6
3	25					92			j = j – 1 = 5
4	25				12				Обмен
5	12				25				i = i + 1 = 2, x = a5
6		57			25				Обмен
7		25			57				j = j – 1 = 4
8		25		37					j = j – 1 = 3
9		25	48						j = j – 1 = 2

В итоге после выполнения процедуры разделения получим:

(12), 25, (48, 37, 57, 92, 86, 33).

Следовательно, исходная задача разбита на две задачи. Применяя процедуру разделения далее, получим:

12, 25, (33, 37), 48, (92, 86, 57)

12, 25, 33, 37, 48, (57, 86), 92

12, 25, 33, 37, 48, 57, 86, 92.

Алгоритм быстрой сортировки не является минимальным по памяти, так как для выполнения рекуррентной процедуры при её моделировании с помощью стека, требуются дополнительные затраты памяти в объёме O(log₂n).

Рассмотрим реализацию алгоритма быстрой сортировки с помощью рекуррентной процедуры с именем SORT(L,R:integer), которая упорядочивает элементы одного массива с индексами от L до R.

a[1..N]

a[L], a[L+1], …, a[R]

Определим процедуру перестановки двух элементов.

procedure SW(I,j:integer);

var x:integer;

begin

x := a[i];

a[i] := a[j];

a[j] := x

end;

Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n.

Рекурсивная реализация быстрой сортировки позволяет устранить этот недостаток путём включения прямого метода сортировки для частей массива с небольшим количеством элементов.

Анализ вычислительной сложности таких алгоритмов показывает, что если подмассив имеет девять или менее элементов, то целесообразно использовать прямой метод (сортировку простыми вставками).