QuickSort.

Определение. Медианой множества А = {a₁ ,…, a_N } называется элемент с индексом (N+1)/2 в отсортированном по возрастанию множестве А.

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

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

В следующей реализации в комментариях показаны соотношения на значения элементов, которые выполняются после каждого шага алгоритма. Эти соотношения доказывают, что каждый раз массив разбивается на части, левая из которых не превосходит медианы, а правая – не меньше медианы. Здесь для простоты множество элементов { A _s , A _s+1 , … , A _t } будем обозначать {s,t}. Медиану будем обозначать M.

QuickSort(A,p,q)

Если q-p < 1 то ВЫЙТИ

Вечный цикл

i=p; j=q; // пусть M=A _j

//цикл 1:

Пока A_i < A _j : i + +;

//{p,i-1}<=M<={j,q}, A_i>=M

поменять местами A _i и A _j ;//M -> A_i

//{p,i}<=M<={j,q}

j --;

//{p,i}<=M<={j+1,q}

Если i >= j то

//либо i==j то {p, j}<=M<={ j+1,q}

// либо i==j+1 то M== A_j+1 => {p, j}<=M<={ j+1,q}

{ QuickSort(A, p, j ); QuickSort(A, j+1, q );ВЫЙТИ }

//цикл 2:

Пока A _j > A_i : j - -;

//{p,i}<=M<={j+1,q}, A _j<=M

поменять местами A _i и A _j ;//x -> A _j

//{p,i}<=M<={j,q}

i + +;

//{p,i-1}<=M<={j,q}

Если i >= j то

//либо i==j то M== A_j => {p, j}<=M<={ j+1,q}

// либо i==j+1 то {p, j}<=M<={ j+1,q}

{ QuickSort(A, p, j ); QuickSort(A, j+1, q );ВЫЙТИ }

Конец вечного цикла

В силу построения алгоритма j не может стать меньше 0 и не может быть больше или равным q, поэтому гарантируется, что мы не попадем в бесконечную рекурсию и границы рассмотрения массива корректны.

Отметим, что после первого цикла также имеем:

Если i >= j то

//либо i==j то {p, i}<=M<={ i+1,q}

// либо i==j+1 то M== A_j+1 => {p, i}<=M<={ i+1,q}

т.е. рекурсию можно было бы организовать в виде:

{ QuickSort(A, p, i ); QuickSort(A, i+1, q );ВЫЙТИ }

но в этом случае мы можем попасть в бесконечную рекурсию, т.к. в цикле i может дойти вплоть до q.

После второго цикла также имеем:

Если i >= j то

//либо i==j то {p, i-1}<=M<={ i,q}

// либо i==j+1 то {p, i-1}<=M<={ i,q}

т.е. рекурсию можно было бы организовать в виде:

{ QuickSort(A, p, i-1 ); QuickSort(A, i, q );ВЫЙТИ }

В этом случае i не может стать меньше 1 и не может быть больше q, поэтому такой вариант алгоритма также возможен.