Главная » Free Pascal » Быстрая сортировка Free Pascal

0

В 1962 г. известный математик Хоар (C. A. R. Hoare) опубликовал алгоритм сортировки, за которым закрепилось название quicksort. Идея этого алгоритма удивительно проста. Сначала выбирается "средний" элемент в сортируемом масси- ве. Все, что больше этого элемента, переносится в правую часть массива, а все, что меньше, — в левую. После первого шага "средний" элемент оказывается на своем месте. Затем аналогичная процедура повторяется для каждой половины массива. На каждом последующем шаге размер обрабатываемого фрагмента массива уменьшается вдвое. Количество операций, которое требуется, в среднем, для реа-

лизации этой процедуры, оценивается константой

n ´ log 2 n . Программа быстрой

сортировки оформлена из процедуры quick, к которой обращается вызывающая

программа, и рекурсивной процедуры qs (листинг 9.14).

   Листинг 9 .1 4 .  Процедура  быстрой  сортировк и  массива  qs                         

procedure qs(var x : array of integer; left, right : integer); var

i, j, xx, yy : integer; begin

i := left; j := right;

xx:= x[(left + right) div 2];

repeat

while (x[i] < xx) and (i < right) do inc(i); while (xx < x[j]) and (j > left) do dec(j); if i <= j then

begin

yy:=x[i]; x[i]:=x[j]; x[j]:=yy; inc(i); dec(j);

end;

until i > j;

if left < j then qs(x, left, j); if i < right then qs(x, i, right);

end;

//———————————————————-

procedure quick(var x: array of integer; n : integer); begin

qs(x,0,n-1); end;

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

редине массива. В самом худшем случае, когда исходный массив уже отсортиро-

ван, такой вариант алгоритма quicksort затратит порядка

O(n2 ) операций.  Суще-

ствует довольно много модификаций алгоритма быстрой сортировки, когда грани- ца разбиения выбирается по-другому. В частности выбор индекса "среднего" элемента организуют случайным образом (random(n)) или как среднее значение между первым, средним и последним элементами массива.

Источник: Кетков, Ю. Л., Свободное программное обеспечение. FREE PASCAL для студентов и школьников, Ю. Л. Кетков, А. Ю. Кетков. — СПб.: БХВ-Петербург, 2011. — 384 с.: ил. + CD-ROM — (ИиИКТ)

По теме:

  • Комментарии