![](/user_photo/2706_HbeT2.jpg)
Лекция 13
Сортировка массивов (продолжение)
Сортировка методом пузырька
На первом шаге проверяются все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева.
На втором шаге свое законное место (второе слева) занимает наименьший из оставшихся элементов массива. И т.д.
Текст процедуры:
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
nCompare:= nCompare +1;
if A[j-1]>A[j] then
begin
x:=A[j-1];
y:= A[j];
A[j-1]:=y;
A[j]:=x;
nMove:= nMove+4;
end;
end;
end;
end;
Количество сравнений:
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 |
… |
… |
… |
… |
|
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 |
Количество переносов:
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 |
∑ |
0 |
2n2-2n |
3/2(n2-n) |
Сортировка методом прямого выбора
На первом шаге разыскивается наименьший из n элементов массива, после чего он обменивается значениями с первым элементом.
На втором шаге разыскивается наименьший из оставшихся n-1 элементов массива, после чего он обменивается значениями с вторым элементом.
И т.д.
Текст процедуры:
procedure StraightSelectionSort;
var
I,j,k: longint;
x: single;
begin
nMove:=0;
nCompare:=0;
for i:=1 to nCurr -1 do
begin
k:=i;
x:=A[k];
nMove:= nMove+1;
for j:=i+1 to nCurr do
begin
nCompare:= nCompare+1;
if A[j]<x then
begin
k:=j;
x:=A[k];
nMove:=nMove+1;
end;
end;
A[k]:=A[i];
A[i]:=x;
nMove:= nMove+3;
end;
end;
Количество сравнений:
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 |
Перед оценкой количества переносов имеет смысл ввести понятие гармонического числа:
Асимптотическая формула для гармонического числа:
,
–
число Эйлера,
.
(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 - Min |
||||||
j=2 |
j=3 |
j=4 |
… |
j |
… |
j=n |
|||
1 |
4 |
4+n-1 |
1/2 |
1/3 |
1/4 |
… |
1/j |
… |
1/n |
2 |
4 |
4+n-2 |
— |
1/2 |
1/3 |
… |
1/(j-1) |
… |
1/(n-1) |
3 |
4 |
4+n-3 |
— |
— |
1/2 |
… |
1/(j-2) |
… |
1/(n-2) |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
i |
4 |
4+n-i |
— |
— |
— |
… |
1/(j-i+1) |
… |
1/(n-i+1) |
… |
… |
… |
— |
— |
— |
… |
… |
… |
… |
n-1 |
4 |
5 |
— |
— |
— |
… |
… |
… |
1/2 |
∑ |
4(n-1) |
n2/2+7n/2-4 |
|
.
(2)
Члены вида
отброшены.
Среднее количество переносов (Никлаус Вирт, «Алгоритмы и структуры данных», стр. 95)
.
(3)
Для численной проверки сделанных оценок предлагается проект ProjectSort, действующий следующим образом.
Массив A заполняется случайными числами с помощью процедуры FillArray.
Проверка того, является ли массив отсортированным, проводится процедурой IsArraySorted – как до сортировки, так и после.
Процедура ShowArray вызывается, при необходимости, для показа массива.
Сортировку изученными методами проводят следующие процедуры:
InsertSort – сортировка вставками,
BubbleSort – сортировка методом пузырька,
StraightSelectionSort – сортировка методом прямого выбора.
Для каждой процедуры сортировки проводится цикл экспериментов, управляемый переменной k. При каждом следующем k число элементов массива nCurr удваивается по сравнению с предыдущим случаем.
M2 – это наблюденное число переносов при последнем значении nCurr.
M1 – это наблюденное число переносов при предыдущем значении nCurr. (И совсем не обязательно, чтобы именно в два раза меньшим).
Если
,
то
,
откуда
,
.
Для рассмотренных сортировок эти формулы позволяют убедиться в верности оценок для среднего числа переносов и сравнений. Для всех случаев, кроме оценки числа переносов в сортировке методом прямого выбора.
program Project1;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}{$IFDEF UseCThreads}
cthreads,
{$ENDIF}{$ENDIF}
Classes
{ you can add units after this };
{$R *.res}
const
nMax = 200000000;
EulerGamma = 0.5772156649015329;
type
ArrayType = array[1 .. nMax] of Single;
SortType=(iInsertSort,iBubbleSort,iStraightSelectionSort);
var
nMove, nCompare: comp;
nCurr, k: longint;
n1,n2: longint;
M1,M2: Comp;
c,b,p,pOur,pVirt: double;
A,A1: ArrayType;
iSortType: SortType;
procedure FillArray;
var
i: integer;
begin
Randomize;
for i:=1 to nCurr do A[i] := Random;
end;
procedure IsArraySorted;
var
i: integer;
begin
for i:=2 to nCurr do
if A[i] < A[i - 1] then
begin
writeln('Array Is NOT Sorted');
Exit;
end;
writeln('Array Is Sorted');
end;
procedure ShowArray;
var
i: integer;
begin
for i:=1 to nCurr do Write(A[i]:8:4)
end;
procedure InsertSort;
var
i, j: integer;
x, y, z: Single;
begin
nMove := 0;
nCompare := 0;
for i := 2 to nCurr do
begin
x := A[i];
nMove:=nMove+1;
j := i;
while (j > 1) and (x < A[j - 1]) do
begin
nCompare:=nCompare+1;
A[j] := A[j - 1];
nMove:=nMove+2;
Dec(j);
end;
A[j] := x;
nMove:=nMove+1;
end;
end;
procedure StraightSelectionSort;
var