Тема 12. Алгоритмы сортировки.

Задача. Сформировать массив из различных элементов.

Алгоритм Пола.

Постановка задачи: необходимо определить наибольший и наименьший элемент линейного массива p и указать их номера.

Алгоритм, предложенный Полом, минимизирует число необходимых сравнений и решает, поставленную задачу за [3*n/2]-2 сравнения.

Идея алгоритма: будем рассматривать пары элементов a[1] и a[2]; a[3] и a[4]… a[2*i-1] и a[2*i]. В каждой паре выберем наибольший и наименьший элементы. Переменной b:=max(a[2;-1], a[2*i]); c:=min(a[2*i-1], [2*i]). На первом шаге b равно наибольшему из первого и второго элементов, а с равно наименьшему из первого и второго элементов. На следующем шаге, наибольший элемент пары сравним с b, а наименьший элемент пары сравним с с. Если “новый” наибольший элемент больше b, то сохраним в b его значение, с с - аналогично.

В общем виде получим:

bi=max(a[2*i-1], a[2*i], bi-1)

ci=min(a[2*i-1], a[2*i], ci-1)

Составим процедуру, реализующую алгоритм Пола:

Procedure FindMaxMinByPd(A:TrealMas, p:integer; var max, min:Real; var Nmax, Nmin:integer);

Var i:integer;

Begin

If a[1]>a[2] then

Begin

Max:=a[1];

Min:=a[2];

NMax:=1;

Nmin:=2;

End

Else

Begin

Max:=a[2];

Min:=a[1];

NMax:=2;

NMin:=1;

End;

For i:=2 to (p div 2) do

Begin

If a[2*i-1]>a[2*i] then

Begin

If a[2*i-1]>max then

Begin

Max:=a[2*i-1];

Nmax:=2*i-1;

End;

If a[2*i]<min then

Begin

Min:=a[2*i];

NMin:=2*i;

End;

End

Else

begin

If a[2*i]>max then

Begin

Max:=a[2*i];

NMax:=2*i;

End;

If a[2*i-1]<min then

Begin

Min:=a[2*i-1];

NMin:=2*i-1;

End;

End;

If (p mod 2)<>0 then

Begin

If a[p]>max then

Begin

Max:=a[p];

NMax:=p;

End;

If a[p]<min then

Begin

Min:=a[p];

NMin:=p;

End;

End;

End;

Замечание: если количество элементов массива нечетно, то выберем наибольший из пары: текущий максимальный и последний элемент и, наименьший из пары: текущий минимальный и последний элемент.

Идея решения: сформируем первый элемент массива случайным образом. Далее сформируем значение для i-го элемента. Если оно содержится среди ранее сформированных, то сформируем его заново. Будем продолжать до тех пор, пока не получим элемент, отличающийся от ранее сформированных. После этого перейдем к генерации следующего элемента.

Воспользуемся функцией FindEquals(A, p, x):boolean;

Составим процедуру генерации массива из различных элементов.

Procedure GetRealVecDif(a, b, p:integer; var RealVec:TrealVec);

Var i:integer;

Begin

RealVec[1]:=a+Random(b-a);

i:=2;

While i<=p do

Begin

RealVec[i]:=a+Random(b-a);

Until FildEquals(RealVec, i-1, RealVec[i])=false;

i:=i+1;

End;

End; {Procedure}.

Замечание: следует отметить, что указанный алгоритм может применяться только в том случае, если (для случая целочисленных массивов) интервал, в котором содержаться сгенерированные элементы, содержит больше р целых чисел. Для вещественных массивов такое ограничение не существенно.