Основной алгоритм
Выберем случайным образом какой-то элемент х и просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший х. Поменяем их местами и продолжим процесс просмотра с обменом, пока просмотры не встретятся где-то в середине массива.
В результате массив разделится на две части: левую - с ключами, меньшими х и правую - с ключами, большими х.
Этот шаг называется разделением. Х - центром.
К получившимся частям рекурсивно применяем ту же процедуру. В результате получается очень эффективная сортировка. Среднее быстродействие O(nlogn), но возможен случай таких входных данных, на которых алгоритм будет работать за O(n^2) операций. Hа случайных входных данных вероятность такого чрезвычайно мала, кроме того, с этим можно бороться при помощи некоторой модификации метода, описанной ниже.
Устойчивости нет. Поведение неестественно.
Пример рекурсивной QuickSort
typedef int item; /* Тип сортируемых элементов */ typedef int tblIndex; /* Тип ключей, по которым сортируем */
#define CompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) { item t, pivot; tblIndex i, j, p;
/********************************** * разделение массива a[lb..ub] * **********************************/
/* Выбираем центр - pivot */ p = lb + ((ub - lb)>>1); pivot = a[p]; a[p] = a[lb];
/* сортируем lb+1..ub относительно центра */ i = lb+1; j = ub; while (1) { while (i < j && compGT(pivot, a[i])) i++; while (j >= i && compGT(a[j], pivot)) j--; if (i >= j) break; t = a[i]; a[i] = a[j]; a[j] = t; j--; i++; }
/* центр в a[j] */ a[lb] = a[j]; a[j] = pivot;
return j; }
void quickSort(T *a, tblIndex lb, tblIndex ub) { tblIndex m;
/************************** * сортируем a[lb..ub] * **************************/
while (lb < ub) {
/* сортировка вставками для малых массивов */ if (ub - lb <= 12) { insertSort(a, lb, ub); return; }
/* разделение пополам */ m = partition (a, lb, ub);
/* Уменьшаем требования к памяти: */ /* меньший сегмент сортируем первым */ if (m - lb <= ub - m) { quickSort(a, lb, m - 1); lb = m + 1; } else { quickSort(a, m + 1, ub); ub = m - 1; } } }
Улучшения
Hа практике для увеличения быстроты, можно произвести несколько улучшений:
Произвести случайную перестановку всех чисел массива перед сортировкой. Алгоритм с этим улушением называется Randomized Quicksort и работает в среднем за O(nlogn) времени при любых неприятных закономерностях в потоке входных данных.
В зависимости от приложения можно использовать этот вариант, либо каждый раз выбирать в качестве центрального для функции partition средний из первого, последнего и среднего элементов. Если же вероятность таких неблагоприятных входных данных крайне мала(массив случаен), то этот пункт можно вовсе опустить.
Для коротких массивов вызывается сортировка вставками. Из-за рекурсии и других "накладных расходов" Quicksort оказывается не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше 12 элементов, вызывается сортировка вставками. Пороговое значение не критично - оно сильно зависит от качества генерируемого кода.
Если последний оператор функции является вызовом этой функции, говорят о хвостовой рекурсии. Ее имеет смысл заменять на итерации - в этом случае лучше используется стек.
После разбиения сначала сортируется меньший раздел. Это также приводит к лучшему использованию стека, поскольку короткие разделы сортируются быстрее и им нужен более короткий стек. Требования к памяти уменьшаются с n до log n. Пример, входящий в стандартную реализацию Си использует многие из этих улучшений.
Стандартная реализация итерационной QuickSort
#include #define MAXSTACK (sizeof(size_t) * CHAR_BIT)
static void exchange(void *a, void *b, size_t size) { size_t i;
/****************** * обменять a,b * ******************/
for (i = sizeof(int); i <= size; i += sizeof(int)) { int t = *((int *)a); *(((int *)a)++) = *((int *)b); *(((int *)b)++) = t; } for (i = i - sizeof(int) + 1; i <= size; i++) { char t = *((char *)a); *(((char *)a)++) = *((char *)b); *(((char *)b)++) = t; } }
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { void *lbStack[MAXSTACK], *ubStack[MAXSTACK]; int sp; unsigned int offset;
lbStack[0] = (char *)base; ubStack[0] = (char *)base + (nmemb-1)*size; for (sp = 0; sp >= 0; sp--) { char *lb, *ub, *m; char *P, *i, *j;
lb = lbStack[sp]; ub = ubStack[sp];
while (lb < ub) {
/* выбираем центр и меняемся с 1м элементом */ offset = (ub - lb) >> 1; P = lb + offset - offset % size; exchange (lb, P, size);
/* разделение в два сегмента */ i = lb + size; j = ub; while (1) { while (i < j && compar(lb, i) > 0) i += size; while (j >= i && compar(j, lb) > 0) j -= size; if (i >= j) break; exchange (i, j, size); j -= size; i += size; }
/* центр в A[j] */ exchange (lb, j, size); m = j;
/* Меньший сегмент продолжаем обрабатывать, больший - в стек */ if (m - lb <= ub - m) { if (m + size < ub) { lbStack[sp] = m + size; ubStack[sp++] = ub; } ub = m - size; } else { if (m - size > lb) { lbStack[sp] = lb; ubStack[sp++] = m - size; } lb = m + size; } } } }
8 8 8
| |