Сортировка методом прямого выбора

Begin

Begin

Begin

Begin

Var

i,j,k: longint;

x,y: single;

nMove:=0;

nCompare:=0;

for i:=2 to nCurr do

for j:= nCurr downto i do

x:= A[j-1];

y:= A[j];

Inc(nMove, 2);

Inc(nCompare);

// if A[j - 1] > A[j] then

if x > y then

A[j - 1]:= y;

A[j]:= x;

Inc(nMove, 2);

end;

end;

end;

end;

Количество сравнений (nCompare):

i	Min	Max	Average
	n -1	n -1	n -1
	n -2	n -2	n -2
	n -3	n -3	n -3
…	…	…	…
i	n - i +1	n - i +1	n - i +1
…	…	…	…
n
∑	n ^2/2- n /2	n ^2/2- n /2	n ^2/2- n /2

Количество переносов (nMove):

i	Min	Max	Average
	2(n -1)	4(n -1)	3(n -1)
	2(n -2)	4(n -2)	3(n -2)
	2(n -3)	4(n -3)	3(n -3)
…	…	…	…
i	2(n - i +1)	4(n - i +1)	3(n - i +1)
…	…	…	…
n
∑	n ^2- n	2 n ^2-2 n	3/2(n ^2- n)

На первом шаге разыскивается наименьший из n элементов массива, после чего он обменивается значениями с первым элементом.

На втором шаге разыскивается наименьший из оставшихся n -1 элементов массива, после чего он обменивается значениями с вторым элементом.

И т.д.

Текст процедуры:

procedure StraightSelectionSort;

Дата добавления: 2014-01-06