Быстрая сортировка на Си
Алгоритм разработан английским информатиком Хоаром, и его часто именуют в честь создателя. Быстрая сортировка относится к алгоритмам “разделяй и властвуй”. Алгоритм можно применять для типов данных, для которых определена операция сравнения.
У быстрой сортировки множество достоинств. Это быстродействующий алгоритм применимый для разных типов данных. Его просто запомнить, следовательно, можно быстро реализовать на практике. Кроме того алгоритм включен в стандартные библиотеки некоторых языков. Алгоритм сочетается с кэшированием, может выполняться в виде параллельных процессов.
Алгоритм быстрой сортировки
В начале выбирается опорный элемент (pivot), от выбора этого элемента может зависеть эффективность алгоритма. Все остальные элементы массива сравниваются с опорным и разделяются на три группы: такие же по величине, большие и меньшие. Для двух последних групп алгоритм запускается с начала.
Алгоритм в общем виде не является устойчивым. Это означает, что в процессе работы элементы с одинаковым значением могут меняться местами.
Для работы с числовыми значениями это может быть незначительно, но с более сложными структурами может вредить. Например, для данных уже отсортированных по одному параметру, при сортировке по другому параметру неустойчивость алгоритма сведет на нет работу предыдущей функции.
Выбор опорного элемента
Есть несколько способов выбрать опорный элемент. В начале использования алгоритма брали первый элемент массива. Этот способ прост в реализации, но его эффективность может быть низка.
Разбиение Ламуто
Алгоритм в этом случае хранит индекс меньшего элемента, когда при прохождении массива встречается элемент меньше чем опорный их меняют местами, а индекс для опорного элемента увеличивают на единицу. Этот алгоритм просто реализовать, но его эффективность может быть очень низкой. Например, если запустит такой алгоритм на уже отсортированном массиве или массиве с равными элементами, в этом случае алгоритм будет работать долго O(n2).
Разбиение Хоара
В этом случае используются два элемента из разных концов массива. Опорным элементом становиться равноудаленный от этих двух выбранных элементов. В некоторых случаях вместо использования реального элемента опорным становится среднее значение меньшего и большего элементов: pivot = (A[low] + A[high])/2.
Алгоритм ищет два элемента один из которых больше опорного и расположен перед ним, а другой меньше и расположен за ним. Найденные элементы меняются местами. Такая схема работает эффективнее, чем предыдущая, потому что позволяет совершать меньше обменов. Недостатком является низкая скорость работы на уже отсортированном массиве. Данный вариант алгоритма нестабилен.
Если в массиве много повторяющихся элементов, то применяют “толстое разбиение”. Особенностью подобного случая является стремление разбить элементы на три, приблизительно равные, части. Для этого перед запуском алгоритма сортировки следует найти самый часто встречающийся элемент и использовать его как опорный. Это позволяет увеличить скорость сортировки для массивов с повторяющимися элементами.
Оценка алгоритма
Методы сортировки сравнивают по скорости их выполнения и дополнительной памяти, необходимой для работы алгоритма.
Производительность
В лучшем случае алгоритм будет делить массив на приблизительно равные части. Разделение массива занимает O(log n) времени. Работа с каждой из частей на каждом подуровне добавит O(n), что даст сложность O(n log n).
Наихудший случай приводит к значительной деградации производительности. Если на протяжении всего выполнения алгоритма разбиение возвращает n-1 элемент для одного из подсписков, то затрачиваемое время оценивается как O(n2). В среднем предложенный алгоритм выполняется за O(n log n).
Затрачиваемая память
Некоторым алгоритмам для работы нужна дополнительная память. Если выделение памяти зависит от размера массива, то при работе с большими объемами данных могут возникать проблемы.
Обычно алгоритм потребляет О(1) дополнительной памяти. В худшем случае может потребоваться O(n) вспомогательного пространства. Потребление памяти может являться следствием не оптимизированного алгоритма, или дополнительная память может использоваться для реализации устойчивой сортировки.
Реализация алгоритма на C
Есть вариант реализации итеративным методом или с использованием рекурсии.
Рекурсия
Особенность алгоритмов типа разделяй и властвуй в том, что они проще реализуются в виде рекурсии.
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 > 0) {
j—;
}
}
} while (i <= j);if (i < high) {
qsortx(a, i, high);
}
if (j > low) {
qsortx(a, low, j);
}
}
Цикл
Реализация без использования рекурсии выглядит немного сложнее.
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[s->size++] = item;
}int pop(Stack *s) {
if (s->size == 0) {
exit(7);
}
s->size—;
return s->data[s->size];
}
Решение в общем виде:
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);
}
Алгоритм в библиотеках
Алгоритм присутствует в стандартной библиотеке языка с. Каждый раз не нужно переписывать реализацию быстрой сортировки или искать среди собственных проектов ее код, достаточно подключить stdlib и использовать функцию qsort.
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
Параметры, которые нужны функции для работы:
- первым параметром следует передать указатель на первый элемент массива;
- второй параметр – это количество элементов в массиве;
- третий параметр – размер в байтах одного элемента;
- последний параметр – это функция, которая используется для сравнения двух элементов массива.
Функция не возвращает ничего. Результатом ее работы является изменение исходного массива.
#include <stdio.h>
#include <stdlib.h>int values[] = { 88, 56, 100, 2, 25 };
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a — *(int*)b );
}int main () {
int n;// вывод исходного массива
printf(«Before sorting the list is: \n»);
for( n = 0 ; n < 5; n++ ) {
printf(«%d «, values[n]);
}// вызов быстрой сортировки из подключенной библиотеки
qsort(values, 5, sizeof(int), cmpfunc);//
printf(«\nAfter sorting the list is: \n»);
for( n = 0 ; n < 5; n++ ) {
printf(«%d «, values[n]);
}return(0);
}
В результате запуска приведенного выше кода в консоли появятся следующие строки:
Before sorting the list is:
88 56 100 2 25After sorting the list is:
2 25 56 88 100
Улучшения алгоритма
Улучшения стремятся избавить алгоритм от неустойчивости при сортировке, деградации производительности. При использовании рекурсии стоит помнить о возможности переполнения стека.
Для устранения неустойчивости каждый элемент массива дополняют ключом. Сравнение происходит по значениям элемента, а в случае их равенства проверяются значение ключей. Этот метод требует дополнительного использования памяти O(n) и предварительного прохода по всем элементам массива для сохранения ключей.
С ухудшением производительности борются при помощи опорного элемента. Выбирают средний элемент, медиану из трех элементов или используют случайный выбор. Накладные расходы для подобных операций не велики. Но это не защищает от данных подходящих под определение худшего случая для этого алгоритма.
Чтобы не произошел отказ из-за превышения глубины рекурсии, можно переходить на другой способ сортировки при достижении определенного количества вызовов. Другой вариант – это сократить число вызовов используя вместо одного из них цикл в пределах этого же вызова.
