Сортировка методом прямого обмена

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

Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы (рисунок 21).

Метод сортировки	Пример [программа pr_18]
for(i=0; i<N; i++) { for(j=N-1; j>i; j--) if(a[j-1]>a[j]) { vsp = a[j]; a[j] = a[j-1]; a[j-1] = vsp; } }	Рисунок 22. Пример сортировки методом прямого обмена

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