Вопрос 31.1. В чем состоит алгоритм "быстрой сортировки"

Сортировка - процесс, позволяющий упорядочить множество однотипных данных в возрастающем или убывающем порядке.

Если сортируемый файл целиком помещается в память (или целиком помещается в массив, то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.

Главное отличие между ними состоит в том, что при внутренней сортировке любая запись - легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками.

Метод быстрой сортировки, разработанный и названный так его автором C.A.R. Hoare, по своим показателям превосходит все остальные алгоритмы, рассмотренные в данной работе. Более того, он считается наилучшим из разработанных на сегодняшний день универсальных алгоритмов. В его основе лежит метод перестановок.

Алгоритм быстрой сортировки построен на основе идеи разбиения массива на разделы. Общая структура заключается в выборе пограничного значения, называемого компарандом (comparand), которое разбивает сортируемый массив на две части. Все элементы, значение которых больше пограничного значения, переносятся в один раздел, а все элементы с меньшими значениями - в другой. Затем этот же процесс повторяется для каждой из частей и так до тех пор, пока массив не будет отсортирован.

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

Среднее число выполняемых сравнений для алгоритма быстрой сортировки равно . Среднее количество перестановок приблизительно равно . Эти числа существенно меньше, чем соответствующие показатели любого из раннее рассмотренных методов сортировки.

Следует иметь в виду один аспект алгоритма быстрой сортировки. Если значение - компаранд для каждого из разделов является максимальным, то алгоритм становится очень медленным, со временем выполнения, пропорциональным квадрату количества элементов. Однако, как правило, этого не происходит.

void qs(int *array, int left, int right)

{

int i, j, comp, temp;

i = left; j = right;

comp = array[(left + right) / 2];

do {

while (array[i] < comp && i < right) i++;

while (array[j] > comp && j > left) j--;

if (i <= j) {

temp = array[i];

array[i] = array[j];

array[j] = temp;

i++; j--;

}

} while (i <= j);

if (left < j) qs(array, left, j);

if (i < right) qs(array, i, right);

}

void quick_sort(int *array, int n)

{

qs(array, 0, n-1);

}