Сортировка методом пузырька
Begin
Begin
Begin
Begin
Begin
Var
Сортировка вставками
Алгоритм, в нескольких словах, таков.
На «первом» шаге вообще ничего не делается.
На втором шаге берётся второй элемент (A2) и сравнивается с первым (A1). Если второй элемент меньше первого, они обмениваются местами. Результат – два элемента упорядочены.
На i-ом шаге (теперь i = 3, 4, 5, … , n) берётся i-ый элемент (Ai) и сравнивается с теми элементами Aj , что расположены слева от него: j = i -1, j = i -2, j = i -3, и т.д. – так до тех пор, пока выполняется неравенство Ai < Aj. В последний раз, когда это неравенство будет выполнено, переменная j примет значение, равное новому месту для Ai – такому, куда нужно Ai вставить.
Например, пусть i = 5, а первые 5 элементов массива таковы:4, 3, 9, 11, 5. В последний раз Ai < Aj при j = 3. Следовательно, число 5 должно встать на третью позицию, подвинув числа 9, 11 вправо на 1 шаг. Результат – i элементов упорядочены.
Текст процедуры:
procedureInsertSort;
i, j: int64;
x: single;
nMove:=0;
nCompare:=0;
fori := 2 tonCurr 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;
ifj > 1 then
// Сюда попали => при последнем j проверка «(x < A[j - 1])» была
Inc(nMove);
// Прверка условия «(x < A[j - 1])» требует одного перемещения
Inc(nCompare);
end;
ifj <> 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
| 
n2/2-n/2
| 
n2/4+n/4-1/2
|
Количество переносов (nMove):
| i | Min | Max | Average |
| … | … | … | … |
| i
| 2i | i+1 | |
| … | … | … | … |
| n | 2n | n+1 | |
| ∑ | 
2(n-1)
| 
n2+n-2
| 
n2/2-3n/2-2
|
На первом шаге проверяются все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева.
На втором шаге свое законное место (второе слева) занимает наименьший из оставшихся элементов массива. И т.д.
Текст процедуры:
procedureBubbleSort;