Сортировка методом пузырька
На первом шаге проверяются все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева.
На втором шаге свое законное место (второе слева) занимает наименьший из оставшихся элементов массива. И т.д.
Текст процедуры:
procedure BubbleSort;
var
i,j,k: longint;
x,y: single;
begin
nMove:=0;
nCompare:=0;
for i:=2 to nCurr do
begin
for j:= nCurr downto i do
begin
x := A[j-1];
y := A[j];
Inc(nMove, 2);
Inc(nCompare);
// if A[j - 1] > A[j] then
if x > y then
begin
A[j - 1] := y;
A[j] := x;
Inc(nMove, 2);
end;
end;
end;
end;
Количество сравнений (nCompare):
i |
Min |
Max |
Average |
2 |
n-1 |
n-1 |
n-1 |
3 |
n-2 |
n-2 |
n-2 |
4 |
n-3 |
n-3 |
n-3 |
… |
… |
… |
… |
i |
n-i+1 |
n-i+1 |
n-i+1 |
… |
… |
… |
… |
n |
1 |
1 |
1 |
∑ |
n2/2-n/2 |
n2/2-n/2 |
n2/2-n/2 |
Количество переносов (nMove):
i |
Min |
Max |
Average |
2 |
2(n-1) |
4(n-1) |
3(n-1) |
3 |
2(n-2) |
4(n-2) |
3(n-2) |
4 |
2(n-3) |
4(n-3) |
3(n-3) |
… |
… |
… |
… |
i |
2(n-i+1) |
4(n-i+1) |
3(n-i+1) |
… |
… |
… |
… |
n |
2 |
4 |
3 |
∑ |
n2-n |
2n2-2n |
3/2(n2-n) |
Сортировка методом прямого выбора
На первом шаге разыскивается наименьший из n элементов массива, после чего он обменивается значениями с первым элементом.
На втором шаге разыскивается наименьший из оставшихся n-1 элементов массива, после чего он обменивается значениями с вторым элементом.
И т.д.
Текст процедуры:
procedure StraightSelectionSort;
var
i, j, k: int64;
x, y, z: single;
begin
nMove := 0;
nCompare := 0;
for i := 1 to nCurr -1 do
begin
k := i;
x := A[i];
z := x;
Inc(nMove);
for j := i + 1 to nCurr do
begin
y := A[j];
Inc(nMove);
Inc(nCompare);
if y < x then
begin
k := j; x := y;
end;
end;
if k <> i then
begin
A[k] := z; A[i] := x;
Inc(nMove, 2);
end;
end;
end;
Количество сравнений (nCompare):
i |
Min |
Max |
Average |
1 |
n-1 |
n-1 |
n-1 |
2 |
n-2 |
n-2 |
n-2 |
3 |
n-3 |
n-3 |
n-3 |
… |
… |
… |
… |
i |
n-i |
n-i |
n-i |
… |
… |
… |
… |
n-1 |
1 |
1 |
1 |
∑ |
n2/2-n/2 |
n2/2-n/2 |
n2/2-n/2 |
Количество переносов (nMove):
i |
Min |
Max |
Average |
1 |
n |
n+2 |
n+1 |
2 |
n-1 |
n+1 |
n+2 |
3 |
n-2 |
n |
n-3 |
… |
… |
… |
… |
i |
n-i+1 |
n-i+3 |
n-i |
… |
… |
… |
… |
n-1 |
2 |
4 |
1 |
∑ |
n2/2+n/2-1 |
n2/2+n*3/2+1 |
n2/2+n/2 |
Количество переносов с диска (nMoveFromDisk):
i |
Min |
Max |
Average |
1 |
n |
n |
n |
2 |
n-1 |
n-1 |
n-1 |
3 |
n-2 |
n-2 |
n-2 |
… |
… |
… |
… |
i |
n-i+1 |
n-i+1 |
n-i+1 |
… |
… |
… |
… |
n-1 |
2 |
2 |
2 |
∑ |
n2/2+n/2-1 |
n2/2+n/2-1 |
n2/2+n/2-1 |
Количество переносов на диск (nMoveToDisk):
i |
Min |
Max |
Average |
1 |
0 |
2 |
? |
2 |
0 |
2 |
? |
3 |
0 |
2 |
? |
… |
… |
… |
… |
i |
0 |
2 |
? |
… |
… |
… |
… |
n-1 |
0 |
2 |
? |
∑ |
0 |
2n-2 |
? |
Количество безусловных переносов в памяти (nMoveInMemoryConst):
i |
Min |
Max |
Average |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
3 |
1 |
1 |
1 |
… |
… |
… |
… |
i |
1 |
1 |
1 |
… |
… |
… |
… |
n-1 |
1 |
1 |
1 |
∑ |
n-1 |
n-1 |
n-1 |
Перед оценкой количества «случайных» переносов имеет смысл ввести понятие гармонического числа:
Асимптотическая формула для гармонического числа:
,
– число Эйлера,
.
(1)
Результаты применения формулы (1):
|
3 |
4 |
5 |
6 |
7 |
8 |
|
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 |
|||
1 |
n |
2n-1 |
1/2 |
1/3 |
1/4 |
… |
1/j |
… |
1/n |
2 |
n-1 |
2n-3 |
— |
1/2 |
1/3 |
… |
1/(j-1) |
… |
1/(n-1) |
3 |
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 |
2 |
3 |
— |
— |
— |
… |
… |
… |
1/2 |
∑ |
n2/2+n/2-1 |
n2-1 |
|
||||||
=???
.
(2)
Члены вида
отброшены.
Для численной проверки сделанных оценок предлагается проект, действующий следующим образом.
Массив A заполняется случайными числами с помощью вспомогательной процедуры FillArray.
Проверка того, является ли массив отсортированным, проводится процедурой IsArraySorted – как до сортировки, так и после.
Процедура ShowArray вызывается, при необходимости, для показа массива.
Сортировку изученными методами проводят следующие процедуры:
InsertSort – сортировка вставками,
BubbleSort – сортировка методом пузырька,
StraightSelectionSort – сортировка методом прямого выбора.
Для каждой процедуры сортировки проводится цикл экспериментов, управляемый параметром цикла k. При каждом следующем k число элементов массива nCurr удваивается по сравнению с предыдущим случаем.
– это наблюденное
число переносов при последнем значении
nCurr.
– это наблюденное
число переносов при предыдущем значении
nCurr.
(И совсем не обязательно, чтобы именно
в два раза меньшим).
Если
,
то
,
откуда
,
.
Для рассмотренных сортировок эти формулы позволяют убедиться в верности оценок для среднего числа переносов и сравнений. Для всех случаев, кроме оценки числа «случайных» переносов в памяти в сортировке методом прямого выбора.