Реализация рекурсивной быстрой сортировки

Размещено на http://www.allbest.ru/

QuickSort

Быстрая сортировка(Quick Sort, QSort) -- сортировка, основанная на сравнениях, широко используется на практике из-за быстрой работы в большинстве случаев. Эта сортировка не является стабильной, реализуется рекурсивно.

QSort -- классический пример принципа разделяй и властвуй.

QSort традиционно реализуется как функция, которой на вход подается массив a и значения l и r. Вызов QSort(a,l,r) сортирует участок массива с индексами от l до r включительно. Для полной сортировки массива нужно вызвать QSort(a,0,n-1). Общий принцип работы Qsort следующий:

1. Выбирается опорное значение x, равное

x=a[i]

2. С помощью индексов i и j массив а делится на три части:

a) [l,i)содержит все элементы, меньше х

б) [j,i)содержит все элементы, равные х

в) [i,r]содержит все элементы, больше х

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

В зависимости от выбора опорного элемента, изменяется те входные последовательности, на которых алгоритм работает за Размещено на http://www.allbest.ru/

, поэтому используют различные подходы к выбору опорного элемента, основная цель которых -- увеличить вероятность того, что левая и правая части будут разделены примерно поровну:

1. -- очень часто встречается «плохая» входная последовательность элементов

2.

x=a[l](x=a[r])

сортировка быстрый рекурсивный код

-- аналогично предыдущему очень часто будет работать за

3.

x=a[random(l,r)]

-- очень маленькая вероятность долгого времени работы, однако из-за случайности выбора не используется в стандартных пакетах

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

Этап разделения массива на 3 части называется partition и может быть осуществлен за О(n). В предположении, что разделение массива на левую и правую части происходит примерно поровну, время работы алгоритма можно оценить с помощью следующей рекуррентной формулы:

T(n) = 2T(n/2) + O(n).

Несложно доказать, что

T(n)=O(n log(n)).

Суммарное количество действий для фиксированной глубины рекурсии составит O(n), при разделении примерно поровну, максимальная глубина рекурсии составит logn, а следовательно количество действий -- nlog(n).

На самом деле, даже при разделении в пропорции 1:2. Таким образом, разделение в любой, но фиксированной пропорции приводит к логарифмической оценке максимальной глубины, но «равномерность» раздела влияет на величину константы.

Алгоритм этапа partition:

1. Возьмем i=l и j=r

2. Пока a[i] < x, увеличиваем индекс i на единицу.

3. Пока a[j] > x, уменьшаем индекс j на единицу.

4. Если меняем значения a[i] и a[j] местами. Уменьшаем j на 1. Увеличиваем i на 1.

5. Возвращаемся к шагу 2 и продолжаем работу алгоритма, иначе разделение массива на три части по опорному элементу х завершено.

В данной статье я представлю рекурсивный пример реализации быстрой сортировки. Массив, который нужно отсортировать будет глобальным, если же вы захотите сделать его локальным, то просто передавайте его как параметр в функцию. Конечно, после того, как вы сделаете это вам нужно будет использовать template для того, чтобы ваша функция работала со всеми типами данных. Я этим заниматься в рамках данной статьи не буду, поэтому просто приведу код рекурсивной сортировки quicksort:

#include <iostream>

using namespace std;

int a[100];

void quickSort(int l, int r)

{

int x = a[l + (r - l) / 2];

//запись эквивалентна (l+r)/2,

//но не вызывает переполнения на больших данных

int i = l;

int j = r;

//код в while обычно выносят в процедуру particle

while(i <= j)

{

while(a[i] < x) i++;

while(a[j] > x) j--;

if(i <= j)

{

swap(a[i], a[j]);

i++;

j--;

}

}

if (i<r)

quickSort(i, r);

if (l<j)

quickSort(l, j);

}

int main()

{

int n;//количество элементов в массиве

cin >> n;

for(int i = 0; i < n; i++)

{

cin>>a[i];

}

quickSort(0, n-1);

for(int i = 0; i < n; i++)

{

cout<<a[i]<<" ";

}

return 0;

}

Размещено на Allbest.ru