Автор этого алгоритма, видимо, настолько был поражён скоростью его работы, что помимо простого и нескромного названия
"быстрая сортировка" ничего не подобрал. Тем не менее, спустя более 40 лет, этот алгоритм до сих пор остаётся наиболее широко применяемым
и одним из самых эффективных алгоритмов, что оправдывает его название.
Метод основан на подходе "разделяй-и-властвуй" и состоит из следующих шагов:
- Из массива выбирается некоторый опорный элемент a[i];
- Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные a[i], влево от него, а все элементы, большие, либо равные a[i] - вправо;
- Теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого;
- Далее, для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру (шаг 2).
quick_sort( массив a, верхняя граница N )
{
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quick_sort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quick_sort для него.
}
template void quick_sort(T* array, long StartN, long EndN)
{
// На входе - массив a[], N - его последний элемент.
register long i = StartN;
register long j = EndN;
T p = a[(i-j)>>1]; // центральный элемент
T temp;
// процедура разделения
do
{
while(a[i] < p) ++i;
while(a[j] > p) --j;
if(i<=j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
++i;
--j;
}
} while(i<=j);
// рекурсивные вызовы, если есть, что сортировать
if (j>StartN) quick_sort(a, StartN, j);
if (i
