Быстрая сортировка участка массива 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).

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

Предыдущий шаг Содержание Следующий шаг