Обменные сортировки
Обзор алгоритмов сортировки начнем с горячо любимой автором (с методической точки зрения), но с наименее эффективной простой сортировки обменом, или сортировки МЕТОДОМ "ПУЗЫРЬКА". Суть ее заключается в следующем: производится попарное сравнение соседних элементов 0-1,1-2 и т.д. и перестановка, если пара расположена не в порядке возрастания. Просмотр повторяется до тех пор, пока перестановок больше не будет. Метод получил свое название за то, что "более весомые" элементы поднимаются в процессе сортировки к концу массива:
//------------------------------------------------------bk35-03.cpp
//------Сортировка методом "пузырька"
void sort(int A[], int n)
{
int i,found; // Количество сравнений
do { // Повторять просмотр...
found =0;
for (i=0; i<n-1; i++)
if (A[i] > A[i+1]) // Сравнить соседей
{ // Переставить соседей
int cc;
cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
found++;
}
} while(found !=0); //...пока есть перестановки
}
Оценить трудоемкость алгоритма можно через среднее количество сравнений, которое равно ( n*n -n )/2.
ШЕЙКЕР-СОРТИРОВКА учитывает тот факт, что от последней перестановки до конца массива будут находиться уже упорядоченные данные, например:
шаг n 5 7 10 9 8 12 14
5 7 ***** 8 12 14
последняя перестановка 5 7 9 ***** 12 14
5 7 9 8 10 12 14
шаг n+1 ------------
упорядоченная часть
Тогда просмотр имеет смысл делать не до конца массива, а до последней перестановки на предыдущем просмотре. Если же просмотр делать попеременно в двух направлениях и фиксировать нижнюю и верхнюю границы неупорядоченной части, то получим шейкер-сортировку (текст программы найдите в "Вопросах без ответов").
