Учитывая важность алгоритма поиска максимума, о чем мы говорили еще в Главе D, запишем его первый вариант в общем виде, причем будем считать, что доступ к компоненте обеспечивает непосредственно получение ее ключевого значения item.

Алгоритм E2-1 (1) 

type
  index1 = 0..N-1; {N > 1}
  massive1 = array [index1] of item;

function Max (Mas: massive1; left, right: index1): item;
var i: index1; temp: item;
begin
  temp:= Mas[left];
  for i:= left+1 to right do
    if Mas[i] > temp then temp := Mas[i];
  Max := temp
end;
        
procedure ShiftRightArray (var Mas: massive1; ind: index1);
  {сдвиг значений вправо, начиная от позиции ind}
var i: index1;
begin
  for i:= N-1 downto ind do
    Mas[i] := Mas[i-1]
end; {ShiftRightArray}

procedure InsArray (var Mas: massive1; K: index1; Elem: item);
var i: index1;
begin
  ShiftRightArray (Mas, k);
  Mas[K] := Elem
end; {InsArray}
            
type
  index1 = 0..N-1; {N > 1}
  massive1 = array [index1] of item;

function Partition
  (var Mas: massive1; left, right: index1): index1;
var i, j: index1; barrier: item;
begin
  barrier := Mas[(left + right) div 2];
  i := left;
  j := right;
  repeat
    while (Mas[i] < barrier) do i := i+1;
    while (Mas[j] > barrier) do j := j-1;
    if i ? j then begin
      Swap{Mas[i], Mas[j]}; i := i+1; j:= j-1
    end;
  until i > j;
  Partition := j
end;

Обратите внимание, что описание функции Max с тремя указанными параметрами делает возможным возврат наибольшего элемента не обязательно для всего массива, но также и любого его подмассива. Для этого при вызове достаточно заменить границы диапазона обработки, входящего в интервал 0..N-1. Мы еще встретимся с таким применением механизма, например, при обсуждении одного из алгоритмов сортировки вектора.

Для второго варианта алгоритма, когда требуется установить местоположение искомого элемента в массиве, нужно лишь незначительно изменить обработку.


Алгоритм E2-1 (2) 

function IndexMax (Mas: massive1; left, right: index1): index1;
var i, temp: index1;;
begin
  temp:= left;
  for i:= left+1 to right do
    if Mas[i] > Mas[temp] then temp := i;
  IndexMax := temp
end;
        
procedure PseudoDelArray (var Mas: massive1; K: index1);
begin
  Swap (Mas[K], Mas[N-1]);
end;
        
procedure QuickSort (var Mas: massive1; left, right: index1);
var ind : index1;
begin
  ind := Partition (Mas, left, right);
  if ind > left then QuickSort (Mas, left, ind);
  if ind+1 < right then QuickSort (Mas, ind+1, right);
end; {Partition}

Очевидно, значение наибольшего элемента доступно в ячейке Mas[IndexMax].

Не исключена ситуация, когда в массиве присутствуют несколько равных по значению "наибольших" элементов. Если для алгоритма E2-1 (1) это обстоятельство несущественно, то, применяя E2-1 (2), нужно иметь в виду, что алгоритм возвращает местоположение первого слева из подходящих элементов.

Назад