Сортировка методом пузырька. Сортировка вставками

Begin

Begin

Begin

Begin

Begin

Var

Сортировка вставками

Алгоритм, в нескольких словах, таков.

На «первом» шаге вообще ничего не делается.

На втором шаге берётся второй элемент (A ₂) и сравнивается с первым (A ₁). Если второй элемент меньше первого, они обмениваются местами. Результат – два элемента упорядочены.

На i -ом шаге (теперь i = 3, 4, 5, …, n) берётся i -ый элемент (A_i) и сравнивается с теми элементами A_j, что расположены слева от него: j = i - 1, j = i - 2, j = i - 3, и т.д. – так до тех пор, пока выполняется неравенство A_i < A_j. В последний раз, когда это неравенство будет выполнено, переменная j примет значение, равное новому месту для A_i – такому, куда нужно A_i вставить.

Например, пусть i = 5, а первые 5 элементов массива таковы: 4, 3, 9, 11, 5. В последний раз A_i < A_j при j = 3. Следовательно, число 5 должно встать на третью позицию, подвинув числа 9, 11 вправо на 1 шаг. Результат – i элементов упорядочены.

Текст процедуры:

procedure InsertSort;

i, j: int64;

x: single;

nMove:=0;

nCompare:=0;

for i:= 2 to nCurr do

x:= A[i];

Inc(nMove);

j:= i;

while (j > 1) and (x < A[j - 1]) do

// Попаданий в тело цикла будет на 1 меньше,

// чем вычислений логического условия « (j > 1) and (x < A[j - 1])».

Inc(nCompare);

A[j]:= A[j - 1];

Inc(nMove, 2);

Dec(j);

end;

if j > 1 then

// Сюда попали => при последнем j проверка «(x < A[j - 1])» была

Inc(nMove);

// Прверка условия «(x < A[j - 1])» требует одного перемещения

Inc(nCompare);

end;

if j <> i then

A[j]:= x;

Inc(nMove);

end;

end;

end;

Назначение переменных:

nCurr – текущее количество элементов в массиве,

nMove – найденное количество перемещений.

nCompare – найденное количество сравнений.

Количество сравнений (nCompare):

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

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

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

На первом шаге проверяются все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева.

На втором шаге свое законное место (второе слева) занимает наименьший из оставшихся элементов массива. И т.д.

Текст процедуры:

procedure BubbleSort;

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