Лекция 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
…	…	…	…
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

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

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 удваивается по сравнению с предыдущим случаем.

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

M₁ – это наблюденное число переносов при предыдущем значении 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