Быстрая сортировка
Быстрая сортировка
Алгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n2, хотя такая ситуация довольно редкая. Быстрая сортировка обычно быстрее других "скоростных" сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая. Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.
Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки. При этом известно, что для каждого болта из ведра есть соответствующая ему по размеру гайка, и для каждой гайки есть соответствующий по размеру болт. Одна беда - у вас отключили свет и вы не можете сравнить болт с болтом и гайку с гайкой. Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача - найти для каждой гайки соответствующий ей болт.
Пусть у нас n пар болт-гайка. Самое простое решение - "в лоб" - берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку, находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + ... + 1 = n2/2 шагов. Существует ли более простое решение?
Самое быстрое (из известных мне) решение не самое очевидное. Применим подход "разделяй и властвуй". Если множество, которое мы хотим обработать слишком большое, то разобьём его на более мелкие и применим рекурсивно наш алгоритм к каждому из них. В конце концов, когда данных будет немного, обработаем и обратно соберём их вместе.
Возьмём любой (случайный) болт и с его помощью разобьём все гайки на те, которые меньше, и те которые больше, чем нужно для этого болта. Конечно, во время разбиения мы найдём и соответствующую ему гайку. Таким образом мы получим две кучи гаек - те, которые больше и те, которые меньше. С помощью найденной гайки разобьём все болты на те, которые меньше, и те, которые больше, чем первоначальный болт. Получим две кучи болтов, мелкие и крупные.
Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой "подкуче". Таким образом, предстоит сделать порядка n·log(n) шагов.
Алгоритм быстрой сортировки напоминает решение нашей задачи. Сначала мы находим опорный элемент - это случайный элемент из множества, относительно которого мы будем проводить разбиение. Далее разобьём множество на три - элементы, которые больше опорного, равны ему и элементы, которые меньше. После чего рекурсивно применим алгоритм к двум оставшимся подмножествам (меньше и больше), если их длина больше единицы.
Рекурсивное решение
Функция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая - длина массива минус один. Нам понадобятся следующие переменные
size_t i, j;
указывают на левый и правый элементы,
int tmp, pivot;
первая переменная для обмена при сортировке, вторая будет хранить значение опорного элемента. Сначала задаём начальные значения
i = low; j = high; pivot = a[(low + (high-low)/2)];
Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного, то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n2. Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов.
Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы
do {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
Далее, если границы ещё не пересеклись, то в случае, если порядок нарушен, то следует обменять местами переменные, после чего опять инкрементировать i и декрементировать 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 > 0) {
j--;
}
}
} while (i <= 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[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);
}
