9.9. Сортировка с помощью прямого обмена

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

Пусть задан массив a размером n. Начинаем просмотр массива с первой пары элементов a[1] и a[2]. Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем их без изменения и сравниваем вторую пару элементов а[2] и а[3]. Если а|2] > а[3], то меняем их местами и т.д. На первом шаге будут просмотрены все пары элементов массива: а[i] и а[i+1] для i от 1 до n -1. В результате такого просмотра и необходимых обменов максимальный элемент переместится в конец массива и будет являться отсортированной частью. На втором шаге аналогичная процедура проводится с первого до (n - 1)-гo элемента. Тем самым второй по величине элемент массива переместится на предпоследнее место. Отсортированная часть будет содержать два элемента. Эти действия продолжаются до тех пор, пока количество элементов в неотсортированной части массива не уменьшится до двух. Нa последнем шаге выполняется упорядочение оставшихся двух элементов. После (n - 1) шагов массив окажется отсортированным по неубыванию. Для иллюстрации отсортируем массив по неубыванию методом простого обмена. Отсортированная часть выделена полужирным шрифтом.

Исходный массив:	22	-14	13	28	6	41	-5	18	0	35	6	-15
1-й шаг	-14	13	22	6	28	-5	18	0	35	6	-15	41
2-й шаг:	-14	13	6	22	-5	18	0	28	6	-15	35	41
3-й шаг:	-14	6	13	-5	18	0	22	6	-15	28	35	41
4-й шаг:	-14	6	-5	13	0	18	6	-15	22	28	35	41
5-й шаг:	-14	-5	6	0	13	6	-15	18	22	28	35	41
6-й шаг:	-14	-5	0	6	6	-15	13	18	22	28	35	41
7-й шаг:	-14	-5	0	6	-15	6	13	18	22	28	35	41
8-й шаг:	-14	-5	0	-15	6	6	13	18	22	28	35	41
9-й шаг:	-14	-5	-15	0	6	6	13	18	22	28	35	41
10-й шаг:	-14	-15	-5	0	6	6	13	18	22	28	35	41
11-й шаг:	-15	-14	-5	0	6	6	13	18	22	28	35	41

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