|
Страница 10 из 60
Быстрая сортировка
Метод быстрой сортировки был разработан Ч.Ф.Р.Хоаром и он же
дал ему это название. В настоящее время этот метод сортировки
считается наилучшим. Он основан на использовании обменного метода
сортировки. Это тем более удивительно, если учесть очень низкое
быстродействие сортировки пузырьковым методом, который представ-
ляет собой простейшую версию обменной сортировки.
В основе быстрой сортировки лежит принцип разбиения. Сначала
выбирается некоторое значение в качестве "основы" и затем весь
массив разбивается на две части. Одну часть составляют все эле-
менты, равные или большие "основы", а другую часть составляют все
элементы меньшего значения, по которому делается разбиение. Этот
процесс продолжается для оставшихся частей до тех пор, пока весь
массив не будет отсортирован. Например, для массива "fedacb" при
использовании в качестве значения разбиения "d" будут получены
следующие проходы при выполнении быстрой сортировки:
- исходное состояние: f e d a c b;
- первый проход: d c a d e f;
- второй проход: a b c d e f.
Этот процесс продолжается для каждой части "вса" и def".
Фактически этот процесс имеет рекурсивную природу. И действти-
тельно, наиболее "аккуратно" быстрая сортировка реализуется пос-
редством рекурсивного алгоритма.
Выбор значения разбиения можно сделать двумя способами. Это
значение можно выбирать случайным образом или путем усреднения
небольшого числа значений, выбранных из массива. Для оптимальной
сортировки требуется выбрать значение, которое будет находиться в
точности посередине всех элементов. Однако, для большинства набо-
ров данных это сделать нелегко. Однако, даже в худшем случае,
когда выбирается одно из экстремальных значений, быстрая сорти-
ровка работает достаточно хорошо.
В приводимом ниже алгоритме быстрой сортировки в качестве
значения разбиения используется среднее значение. Хотя такой под-
ход не всегда является наилучшим, он достаточно прост и сортиров-
ка будет выполняться правильно.
{ быстрая сортировка }
procedure QuickSort(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it: DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i:=l; j:=r;
x:=it[(l+r) div 2];
repeat
while it[i]<x do i := i+1;
while x<it[j] do j := j-1;
if y<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end; { конец быстрой сортировки }
В данном примере процедура быстрой сортировки обращается к
основной процедуре сортировки с именем "qs". Это обеспечивает
доступ к данным "item" и "count" при всех вызовах "qs".
Вывод числа операций сравнения и числа операций обмена для
быстрой сортировки выходит за рамки данной книги. Можно считать,
что число операций сравнения равно n log n, а число операций об-
мена равно приблизительно n/6 log n. Эти характеристики значи-
тельно лучше характеристик рассмотренных ранее сортировок.
Равенство
N = a**x
можно представить в виде
x = log n.
a
Это, например, будет означать, чо при сортировке ста элемен-
тов методом быстрой сортировки потребуется в среднем 100*2, т.е.
200 операций сравнений, так как log 100 равен 2. Это значение яв-
ляется вполне хорошим по сравнению со значением 990 для сортиров-
ки пузырьковым методом.
Однако, следует иметь в виду одно неприятное свойство быст-
рой сортировки. Если выбираемое для разбиения значение оказывает-
ся совпадающим с максимальным значением, то быстрая сортировка
превращается в самую медленную с временем выполнения n . Однако,
на практике этот случай не встречается.
Необходимо тщательно выбирать метод определения значения
разбиения. Часто это значение определяется по фактическим данным,
которые сортируются. Для больших списков почтовых отправлений,
когда сортировка часто делается по коду почтового индекса, значе-
ние для разбиения выбрать не сложно, так как коды почтовых индек-
сов распределены достаточно равномерно и требуемое значение можно
определить с помощью простой алгебраической процедуры. Однако,
определенные базы данных могут иметь ключи сортировки с очень
близкими значениями и поэтому наилучшим методом часто оказывается
случайный выбор значения. Распространенный и достаточно эффектив-
ный метод заключается в выборке трех элементов из соответствующей
области и вычисление их среднего значения. |