Вопрос 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);

}

Вопрос 38.1. Как может быть повышена эффективность реализации "быстрой сортировки"

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

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

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

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

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

Алгоритм быстрой сортировки можно реализовать не только посредством проце­дуры quicksort (см в предыдущем вопросе) так, чтобы среднее время выполнения равнялось О(п log п). Можно создать другие процедуры, реализующие этот алгоритм, которые будут иметь тот же порядок О(п log п) времени выполнения в среднем, но за счет меньшей константы пропорциональности в этой оценке будут работать несколько быстрее (напомним, что порядок времени выполнения, такой как О(п log п), определяется с точностью до константы пропорциональности). Эту константу можно уменьшить, если выбирать опорное (пограничное) значение таким, чтобы оно разбивало рассматриваемое в данный момент подмножество элементов на две примерно равные части. Можно надеяться, что при "правильном" выборе опорного значения выполнение алгоритма ускорится.

Например, можно с помощью датчика случайных чисел выбрать три элемента из подмножества и средний (по величине) из них назначить опорным значением. Можно также, задав некоторое число k, выбрать случайным образом (например, опять с по­мощью датчика случайных чисел) k элементов из подмножества, упорядочить их процедурой quicksort или посредством какой-либо простой сортировки и в качестве опорного значения взять медиану (т.е. (k+1)/2-й элемент) этих k эле­ментов. Заметим в скобках, что интересной задачей является определение наилуч­шего значения А как функции от количества элементов в подмножестве, подлежащем сортировке. Если k очень мало, то среднее время будет близко к тому, как если бы выбирался только один элемент. Если же k очень велико, то уже необходимо учиты­вать время нахождения медианы среди k элементов.

Другие реализации алгоритма быстрой сортировки можно получить в зависимости от того, что мы делаем в случае, когда получаются малые подмножества. При малых п алгоритмы с временем выполне­ния О(п²) работают быстрее, чем алгоритмы с временем выполнения порядка О(п log п). Однако понятие "малости" п зависит от многих факторов, таких как орга­низация рекурсивных вызовов, машинная архитектура и компилятор языка про­граммирования, на котором написана процедура сортировки. Предлага­ется значение 9 в качестве порогового значения размера подмножества, ниже которо­го целесообразно применять простые методы сортировки.

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

Таким образом, можно сделать только п перестановок записей вместо О(п log п) пе­рестановок, и эта разница особенно значительна для больших записей. Отрицательными аспектами такого подхода являются использование дополнительного объема памяти для массива указателей и более медленное выполнение операции сравнения ключей, поскольку здесь сначала, следуя за указателями, надо найти нужные записи, затем необходимо войти в записи и только потом взять значения поля ключа.