Void sort_pair(int* a, int n)

{ int i, k;

for (i = 0; i < n - 1; i++) // множитель n-1

for (k = 0; k < n - 1; k++) // множитель n-1

if (A[k] > A[k+1]) swp(A[k], A[k+1]); // время = с

}

Здесь swp(x,y) - процедура парного обмена (кстати, это реальная функция из модуля syst.h).

Вложенные циклы не зависимы друг от друга. Поэтому:

.

Отсюда, на основании базовой теоремы 1, получаем:

.

3. Метод пузырька

В следующем варианте метода пузырька, алгоритм построен несколько иначе. Вначале среди всех элементов массива находится наибольший и, затем, этот элемент меняется местами с первым элементом массива. На следующем шаге выполняется такая же процедура с отрезком массива "второй элемент - последний элемент". Работа алгоритма завершается после обработки отрезка массива "предпоследний элемент - последний элемент".

Программная реализация алгоритма:

Void sort_bubble(int* a, int n)

{ int i, j, im;

for (i = 0; i < n-1; i++) // суммировать по i от 0 по n-2

{ im = i; // время = c₁

for (j = i+1; j < n; j++) // множитель n-i-1

if (A[j] > A[im]) im = j; // время = c₂ , худший случай

swp(A[im], A[i]); // время = c₃

}

}

Время работы алгоритма можно еще немного уменьшить, если в отрезке массива определять наибольший и наименьший элементы и перемещать их в первую и последнюю позиции отрезка массива соответственно.

Здесь внутренний цикл зависим от внешнего. Оцениваем худший случай. Общее время работы процедуры будет равно:

.

Отсюда:

. .

И тогда:

.

4. Сортировка методом вставки

В этом методе сортируемый массив разбивается на два отрезка: отрезок A[0], ... , A[i-1] предполагается уже упорядоченным, и отрезок A[i], ... , A[n-1] еще не упорядочен. Основной шаг алгоритма состоит в том, что элемент A[i] поочередно сравнивается с элементами упорядоченной части массива A[0], ... , A[i-1] и вставляется в соответствующую ему позицию. Ниже приведена функция insertion, которая упорядочивает массив по возрастанию методом вставки.

Ниже приведен фрагмент процедуры сортировки, необходимый для анализа алгоритма.

for (j = 1; j < n; j++) // внеш. цикл

{ buf = A[j]; i = j-1; // с₁

while (i >= 0 && A[i] > buf) // внутр. цикл

{ A[i+1] = A[i]; i--; } // с₂

A[i+1] = buf; // с₃

}

Время выполнения цикла while в худшем случае равно c₂j . Полное время:

.

После несложных преобразований получаем:

.

Полученная оценка относится к наихудшему случаю. В общем случае будем иметь:

.

5. Метод слияния

Основу метода слияния составляют:

- объединение двух упорядоченных массивов в один (операция слияния);

- последовательное деление исходного массива на все более мелкие части путем использования рекурсивной процедуры с последующим их объединением.

Процедура слияния

Два упорядоченных массива (или два отрезка одного массива) объединяются в один (также упорядоченный) массив. Пусть имеем исходные массивы: А₁ с числом элементов n₁ и A₂ с числом элементов n₂. Рассмотрим процедуру слияния массивов А₁ и A₂ в массив A с числом элементов n = n₁+n₂. Предполагается, что n₁ и n₂ не обязательно совпадают.

На каждом шаге процедуры выполняется следующее:

- выбираем первый элемент массива А₁ и первый элемент массива А₂;

- меньший из них удаляем из соответствующего массива и присоединяем к имеющимся элементам результирующего массива А.

Очевидно, что для выполнения процедуры слияния таких шагов необходимо выполнить n₁+n₂ = n. Отсюда получаем, что время выполнения процедуры слияния будет пропорционально n (говорят, что процедура слияния является линейной по времени).

Последовательное деление

Реализуется путем использования рекурсивной процедуры, предполагающей деление заданного отрезка исходного массива на две по возможности равные части. Процесс деления завершается, если число элементов очередного отрезка равно 1. В итоге исходный массив будет представлять собой последовательность одноэлементных подмассивов.

Рассмотрим в качестве примера 8-элементный массив А = { 5, 2, 4, 6, 1, 3, 2, 6 } . Последовательное объединение подмассивов показано ниже.

Шаг 1: дробление на одноэлементные отрезки: (5), (2), (4), (6), (1), (3), (2), (6)

Шаг 2: объединение одноэл. отрезков: (2 , 5), (4 , 6), (1 , 3), (2 , 6)

Шаг 3: объединение двухэл. отрезков: (2 , 4 , 5 , 6), (1 , 2 , 3 , 6)

Шаг 4: последнее объединение: (1 , 2 , 2 , 3 , 4 , 5 , 6 , 6)

Программная реализация

Ниже приведена программная реализация метода слияния для случая, когда массив упорядочивается по возрастанию.

Вспомогательная процедура слияния merge объединяет два отрезка исходного массива A с границами [p,q] и [q+1,r] и размещает результат в отрезке с границами [p,r].