QuickSort. Первая реализация.

Определение. Медианой множества А = {a1 ,…, aN } называется элемент с индексом (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:

   Пока Ai  < A j :  i + +;

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

   поменять местами A i  и A j ;//M -> Ai

//{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== Aj+1  => {p, j}<=M<={ j+1,q}

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

//цикл 2:

   Пока A j  > Ai :  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== Aj  => {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== Aj+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, поэтому такой вариант алгоритма также возможен.