Сортировка слиянием без рекурсии.

Предыдущий алгоритм можно модифицировать так, что он уже не будет использовать рекурсию. Действительно. Рассмотрим последовательно все пары элементов в сортируемом массиве. Каждый из элементов в паре представляет собой уже отсортированный массив длины 1, поэтому эти массивы (пока длины 1) можно слить в упорядоченные куски длины 2. Далее мы рассматриваем уже пары упорядоченных массивов длины 2 и сливаем их в массивы длины 4. И т.д.

Отметим, что при этих операциях на k- том проходе по упорядочиваемому массиву на правом конце массива мы будем получать либо ситуацию, когда у правого оставшегося куска (длины £ 2^k) вообще нет парного куска для слияния, либо кусок есть и его длина £ 2^k. В первом случае делать вообще ничего не нужно, а во втором следует стандартным способом сливать куски, возможно, существенно различной длины.

Легко видеть, что данный алгоритм решает задачу за время O(N log₂ N), где N – количество элементов в сортируемом массиве.

Лекция 3

Алгоритмы. Сведение алгоритмов.

Сортировки и связанные с ними задачи.

  Д.Кнут. Искусство программирования для ЭВМ. тт 1-3. Москва. Мир. 1996-1998 Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999. Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989  

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;//x -> 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, поэтому такой вариант алгоритма также возможен.

--------------------------------------------------------------------------------

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

---

Дата добавления: 2015-10-30