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

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. Элементы средней части уже заняли свое относительное положение и для полной сортировки массива достаточно отдельно отсортировать левую и правую части, если в них более одного элемента

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

• 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.

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.

quickSort (i, r);

if (l.

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<<<" «;

}.

return 0;

}.