Быстрая сортировка и с чем её едят

• Чулан *

Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

Алгоритм

1. Выбираем опорный элемент
2. Разбиваем массив на 3 части
   • Создаём переменные l и r - индексы соответственно начала и конца рассматриваемого подмассива
   • Увеличиваем l, пока l-й элемент меньше опорного
   • Уменьшаем r, пока r-й элемент больше опорного
   • Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
   • Если l вдруг становится больше r, то прерываем цикл
3. Повторяем рекурсивно, пока не дойдём до массива из 1 элемента

void qsort (int b, int e)
{
int l = b, r = e;
int piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
while (l <= r)
{
while (arr[l] < piv)
l++;
while (arr[r] > piv)
r--;
if (l <= r)
swap (arr, arr);
}
if (b < r)
qsort (b, r);
if (e > l)
qsort (l, e);
} /* ----- end of function qsort ----- */

// qsort (0, n-1);

* This source code was highlighted with Source Code Highlighter .

Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента - один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.

Писáл сам, изредка поглядывая на Википедию . Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!

Теги: Qsort, быстрая сортировка, алгоритмы сортировки, алгоритмы, C

А лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n 2 , хотя такая ситуация довольно редкая. Быстрая сортировка обычно быстрее других "скоростных" сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая. Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.

Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки. При этом известно, что для каждого болта из ведра есть соответствующая ему по размеру гайка, и для каждой гайки есть соответствующий по размеру болт. Одна беда - у вас отключили свет и вы не можете сравнить болт с болтом и гайку с гайкой. Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача - найти для каждой гайки соответствующий ей болт.

Пусть у нас n пар болт-гайка. Самое простое решение - "в лоб" - берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку, находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + ... + 1 = n 2 /2 шагов. Существует ли более простое решение?

Самое быстрое (из известных мне) решение не самое очевидное. Применим подход "разделяй и властвуй". Если множество, которое мы хотим обработать слишком большое, то разобьём его на более мелкие и применим рекурсивно наш алгоритм к каждому из них. В конце концов, когда данных будет немного, обработаем и обратно соберём их вместе.

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

Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой "подкуче". Таким образом, предстоит сделать порядка n·log(n) шагов.

Алгоритм быстрой сортировки напоминает решение нашей задачи. Сначала мы находим опорный элемент - это случайный элемент из множества, относительно которого мы будем проводить разбиение. Далее разобьём множество на три - элементы, которые больше опорного, равны ему и элементы, которые меньше. После чего рекурсивно применим алгоритм к двум оставшимся подмножествам (меньше и больше), если их длина больше единицы.

Рекурсивное решение

Ф ункция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая - длина массива минус один. Нам понадобятся следующие переменные

Size_t i, j;

указывают на левый и правый элементы,

Int tmp, pivot;

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

I = low; j = high; pivot = a[(low + (high-low)/2)];

Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного, то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n 2 . Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов.

Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы

Do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; }

If (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; j--; } } while (i <= j);

Здесь, однако, возможна ошибка. i вряд ли переполнится - размер массива не больше, чем максимальное значение типа size_t, умноженное на размер элемента массива байт (более сложные варианты даже рассматривать не будем). Но вот переменная j вообще-то может перейти через нуль. Так как переменная целочисленная, то при переходе через нуль её значение станет больше, чем i, что приведёт к зацикливанию. Поэтому необходима превентивная проверка.

If (j > 0) { j--; }

После этого цикла i и j пересекутся, i станет больше j и мы получим ещё два массива, для которых следует применить сортировку: массив от левой границы до i, и массив от j до правой границы, если, конечно, мы не вышли за пределы границ.

If (i < high) { qsortx(a, i, high); } if (j > low) { qsortx(a, low, j); }

Void qsortx(int *a, size_t low, size_t high) { size_t i, j; int tmp, pivot; i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; } if (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > <= j); if (i < high) { qsortx(a, i, high); } if (j > low) { qsortx(a, low, j); } }

Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort.

Итеративное решение

Теперь вместо того, чтобы вызывать функцию, будем сохранять в стек крайнее левое и правое значения. Можно сохранять сразу пару значений, но мы вместо этого сделаем два параллельных стека. В первый будем класть крайнее левое значение для следующего вызова, а во второй - крайнее правое. Цикл заканчивается, когда стеки становятся пустыми.

Void qsortxi(int *a, size_t size) { size_t i, j; int tmp, pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size - 1); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; } if (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > 0) { j--; } } } while (i <= j); if (i < high) { push(lows, i); push(highs, high); } if (j > low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); }

Код стека

#define STACK_INIT_SIZE 100 typedef struct Stack { size_t size; size_t limit; int *data; } Stack; Stack* createStack() { Stack *tmp = (Stack*) malloc(sizeof(Stack)); tmp->limit = STACK_INIT_SIZE; tmp->size = 0; tmp->data = (int*) malloc(tmp->limit * sizeof(int)); return tmp; } void freeStack(Stack **s) { free((*s)->data); free(*s); *s = NULL; } void push(Stack *s, int item) { if (s->size >= s->limit) { s->limit *= 2; s->data = (int*) realloc(s->data, s->limit * sizeof(int)); } s->data = item; } int pop(Stack *s) { if (s->size == 0) { exit(7); } s->size--; return s->data; }

Функция в общем виде

Void qsortxig(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i, j; void *tmp, *pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size - 1); tmp = malloc(item); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = (char*)a + (low + (high-low)/2)*item; do { while (cmp(((char*)a + i*item), pivot)) { i++; } while (cmp(pivot, (char*)a + j*item)) { j--; } if (i <= j) { if (cmp((char*)a + j*item, (char*)a + i*item)) { memcpy(tmp, (char*)a + i*item, item); memcpy((char*)a + i*item, (char*)a + j*item, item); memcpy((char*)a + j*item, tmp, item); } i++; if (j > 0) { j--; } } } while (i <= j); if (i < high) { push(lows, i); push(highs, high); } if (j > low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); free(tmp); }