Быстрая сортировка

   
Быстрая сортировка участка массива R от p до rr происходит следующим образом:

  • Элементы массива R переставляются так, что бы любой из элементов R[p], ..., R[q] был не больше любого из элементов R[q+1], ..., R[rr]. Эта операция называется
    разделением (partition). Здесь q — некоторое число в интервале p ≤ q ≤ rr;
  • Процедура сортировки рекурсивно вызывается для массивов R[p..q] и R[q+1, rr].
procedure QuickSortR(p,rr:longint);
var
	q: longint;
begin
	if p < rr then
	begin
		 q:=Partition(p,rr);
		 QuickSortR(p,q);
		 QuickSortR(q+1, rr);
	end;
end;

   
Рассмотрим теперь подробнее реализацию функции Partition(p, rr).

function Partition(p, rr:longint):longint;
  var
    i, j, z : longint;
	x, t : single;
begin  
	  x:= R[p];
	  i:= p - 1;
	  j:= rr + 1;
	  while i < j do
		begin
		  repeat j:= j - 1 until R[j] ≤ x;
		  repeat i:= i + 1 until R[i] ≥ x;
		  if i < j then
			  begin
				t:= R[i]; R[i]:= R[j]; R[j]:= t;
				z:= B[i]; B[i]:= B[j]; B[j]:= z;
				z:= E[i]; E[i]:= E[j]; E[j]:= z;
			  end;
		end;
		Partition:= j;		  
end;

   
В качестве "граничного элемента" принимается X = R[p]. Далее заводим два указателя: i —
при просмотре элементов с начала сортируемого участка, и j — при
просмотре элементов с конца сортируемого участка. Пока i < j, выполняется слeдующее:
находим R[j] — первый с конца элемент меньше Х, и R[i] — первый с начала элемент,
больший X. Если i < j, то меняем местами элементы R[i] и R[j]:

t:= R[i], R[i]:= R[j]; R[j]: = t; 

   
Поскольку в данной задаче нужно синхронно с перемещением весов ребер R[k] перемещать также вершины их начала
и конца, выполняются также соответствующие операции:

z:= B[i]; B[i]:= B[j]; B[j]:= z;
z:= E[i]; E[i]:= E[j]; E[j]:= z;

   
По завершении цикла "пока i < j" мы и получаем границу "разделения" Partition:= j.
Понятно, что вызывать алгоритм быстрой сортировки нужно, передавая ему вначале
номера начального и конечного элементов массива, например, для задачи
"Веревочный телеграф": QuickSortR(1, N * (N - X) div 2).

   
На следующем шаге рассмотрим решение олимпиадной задачи.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий