Лекция 13

Begin

Begin

Begin

Begin

Begin

Var

i, j, k: int64;

x, y, z: single;

nMove:= 0;

nCompare:= 0;

for i:= 1 to nCurr -1 do

k:= i;

x:= A[i];

z:= x;

Inc(nMove);

for j:= i + 1 to nCurr do

y:= A[j];

Inc(nMove);

Inc(nCompare);

if y< x then

k:= j; x:= y;

end;

end;

if k <> i then

A[k]:= z; A[i]:= x;

Inc(nMove, 2);

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	n - i	n - i
…	…	…	…
n -1
∑	n ^2/2- n /2	n ^2/2- n /2	n ^2/2- n /2

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

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

Количество переносов с диска (nMoveFromDisk):

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

Количество переносов на диск (nMoveToDisk):

i	Min	Max	Average
			?
			?
			?
…	…	…	…
i			?
…	…	…	…
n -1			?
∑	0	2 n- 2	?

Количество безусловных переносов в памяти (nMoveInMemoryConst):

i	Min	Max	Average
…	…	…	…
i
…	…	…	…
n -1
∑	n -1	n -1	n -1

Перед оценкой количества «случайных» переносов имеет смысл ввести понятие гармонического числа:

Асимптотическая формула для гармонического числа:

,

– число Эйлера,

. (1)

Результаты применения формулы (1):

	1.83333	2.08333	2.28333	2.45000	2.59286	2.71786
	1.83324	2.08330	2.28332	2.44999	2.59285	2.71786

Количество случайных переносов в памяти:

i	Min	Max	Average
j =2	j =3	j =4	…	j	…	j = n
	n	2 n -1	1/2	1/3	1/4	…	1/ j	…	1/ n
	n -1	2 n -3	—	1/2	1/3	…	1/(j -1)	…	1/(n -1)
	n -2	2 n -5	—	—	1/2	…	1/(j -2)	…	1/(n -2)
…	…	…	…	…	…	…	…	…	…
i	n - i +1	2 n -2 i +1	—	—	—	…	1/(j - i +1)	…	1/(n - i +1)
…	…	…	—	—	—	…	…	…	…
n -1			—	—	—	…	…	…	1/2
∑	n ^2/2+ n /2-1	n ^2-1	=???

.

(2)

Члены вида отброшены.

Для численной проверки сделанных оценок предлагается проект, действующий следующим образом.

Массив A заполняется случайными числами с помощью вспомогательной процедуры FillArray.

Проверка того, является ли массив отсортированным, проводится процедурой IsArraySorted – как до сортировки, так и после.

Процедура ShowArray вызывается, при необходимости, для показа массива.

Сортировку изученными методами проводят следующие процедуры:

InsertSort – сортировка вставками,

BubbleSort – сортировка методом пузырька,

StraightSelectionSort – сортировка методом прямого выбора.

Для каждой процедуры сортировки проводится цикл экспериментов, управляемый параметром цикла k. При каждом следующем k число элементов массива nCurr удваивается по сравнению с предыдущим случаем.

– это наблюденное число переносов при последнем значении nCurr.

– это наблюденное число переносов при предыдущем значении nCurr. (И совсем не обязательно, чтобы именно в два раза меньшим).

Если

,

то

,

откуда

, .

Для рассмотренных сортировок эти формулы позволяют убедиться в верности оценок для среднего числа переносов и сравнений. Для всех случаев, кроме оценки числа «случайных» переносов в памяти в сортировке методом прямого выбора.

Сортировка массивов (продолжение)

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