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

Основное требование для методов сортировки массивов – экономное использование памяти. Это значит, что перераспределение элементов нужно выполнять на том же месте {in site}, и поэтому методы, которые пересылают элементы из массива А в массив В для нас не представляют интереса.

Таким образом, выбирая метод сортировки и руководствуясь критериями экономии памяти, классификацию алгоритмов мы будем проводить в соответствии с их эффективностью, это значит экономией времени и быстротой действия. При этом будем подсчитывать С – необходимое количество сравнений ключей и М – пересылок элементов (что отнимает много времени). Это будут функции от n – числа сортируемых элементов.

Методы, сортирующие элементы in site, можно разбить на три основных класса в зависимости от заложенного в их основе приема (базового алгоритма):

• Сортировка обменом

• Сортировка включениями

• Сортировка выбором

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

При различных методах сортировки интерес будут вызывать такие вопросы:

1. Как ведет себя алгоритм в крайних ситуациях:

• Массив упорядочен в нужном порядке

• Массив упорядочен в обратном порядке

• Массив не упорядочен

2. На каких массивах алгоритм дает:

• Min количество действий

• Max количество действий

• Чему равняется среднее количество действий

2. Сортировки обменом

2.1. Сортировка простым обменом (метод пузырька)

Идея: упорядоченный массив А получается из исходного массива А систематическим обменом пары рядом находящихся элементов, которые не соответствуют нужному порядку упорядочения, пока такие пары находятся при просмотре массива.

Просмотр массива будем осуществлять справа налево (можно и наоборот). Этот алгоритм называется сортировка «пузырьком», поскольку минимальный элемент как бы всплывает (как пузырек) в начало массива при просмотре этого массива.

Рассмотрим работу такого алгоритма на следующем примере (n=8):

44, 55, 12, 42, 94, 18, 06, 67

В следующей таблице в столбцах отражены промежуточные состояния сортируемого массива.

Таблица. Пример сортировки методом пузырька

Начальные ключи	i=2	i=3	i=4	i=5	i=6	i=7	i=8
44	06	06	06	06	06	06	06
55	44	12	12	12	12	12	12
12	55	44	18	18	18	18	18
42	12	55	44	42	42	42	42
94	42	18	55	44	44	44	44
18	94	42	42	55	55	55	55
06	18	94	67	67	67	67	67
67	67	67	94	94	94	94	94

Посчитаем количество сравнений:

Количество пересылок (обменов):

; ; ;

Можно заметить, что массив был отсортирован на некотором промежуточном шаге, однако алгоритм построен так, что это явление в нем не анализируется.