Лекция 13
Begin
Begin
Begin
Begin
Begin
Var
i, j, k: int64;
x, y, z: single;
nMove := 0;
nCompare := 0;
fori := 1 tonCurr -1 do
k := i;
x := A[i];
z := x;
Inc(nMove);
forj := i + 1 tonCurr do
y := A[j];
Inc(nMove);
Inc(nCompare);
ify< x then
k := j; x := y;
end;
end;
ifk <> 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 | |||
| ∑ | 
n2/2-n/2
| 
n2/2-n/2
| 
n2/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 | |||
| ∑ |
n2/2+n/2-1
|
n2/2+n*3/2+1
|
n2/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 | |||
| ∑ |
n2/2+n/2-1
|
n2/2+n/2-1
|
n2/2+n/2-1
|
Количество переносов на диск (nMoveToDisk):
| i | Min | Max | Average |
| ? | |||
| ? | |||
| ? | |||
| … | … | … | … |
| i
| ? | ||
| … | … | … | … |
| n-1 | ? | ||
| ∑ | 0
|
2n-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 | 2n-1 | 1/2 | 1/3 | 1/4 | … | 1/j | … | 1/n | |
| n-1 | 2n-3 | — | 1/2 | 1/3 | … | 1/(j-1) | … | 1/(n-1) | |
| n-2 | 2n-5 | — | — | 1/2 | … | 1/(j-2) | … | 1/(n-2) | |
| … | … | … | … | … | … | … | … | … | … |
| i
| n-i+1 | 2n-2i+1 | — | — | — | … | 1/(j-i+1) | … | 1/(n-i+1) |
| … | … | … | — | — | — | … | … | … | … |
| n-1 | — | — | — | … | … | … | 1/2 | ||
| ∑ |
n2/2+n/2-1
| 
n2-1
|  =???
|
.
(2)
Члены вида 
отброшены.
Для численной проверки сделанных оценок предлагается проект, действующий следующим образом.
Массив A заполняется случайными числами с помощью вспомогательной процедуры FillArray.
Проверка того, является ли массив отсортированным, проводится процедурой IsArraySorted – как до сортировки, так и после.
Процедура ShowArray вызывается, при необходимости, для показа массива.
Сортировку изученными методами проводят следующие процедуры:
InsertSort – сортировка вставками,
BubbleSort – сортировка методом пузырька,
StraightSelectionSort – сортировка методом прямого выбора.
Для каждой процедуры сортировки проводится цикл экспериментов, управляемый параметром цикла k. При каждом следующем k число элементов массива nCurr удваивается по сравнению с предыдущим случаем.
– это наблюденное число переносов при последнем значении nCurr.
– это наблюденное число переносов при предыдущем значении nCurr. (И совсем не обязательно, чтобы именно в два раза меньшим).
Если
,
то
,
откуда
, 
.
Для рассмотренных сортировок эти формулы позволяют убедиться в верности оценок для среднего числа переносов и сравнений. Для всех случаев, кроме оценки числа «случайных» переносов в памяти в сортировке методом прямого выбора.
Сортировка массивов (продолжение)