Программирование на языке высокого уровня. Марапулец Ю.В. - 48 стр.

      Обменная сортировка «пузырьком». Суть данной сортировки заключается в сле-
дующем: производятся попарное сравнение соседних элементов 0 - 1, 1 - 2 ... и переста-
новка, если пара расположена не в порядке возрастания. Просмотр повторяется до тех
пор, пока при пробегании массива от начала до конца перестановок больше не будет.

void sort_bubble (int A[], int n)
{
        int i, k;                 // Количество сравнений
        do                               // Повторять просмотр...
        {
                 k = 0;
                 for (i=0; i A[i+1])      // Сравнить соседей
                         {
                                 int buf = A[i];        // Переставить соседей
                                 A[i]=A[i+1];
                                 A[i+1]=buf;
                                 k++;
                        }
        }
        while(k != 0);                   //пока есть перестановки
}

     Оценить трудоемкость алгоритма можно через среднее количество сравнений, ко-
торое равно (N*N - N)/2. Обменные сортировки имеют ряд особенностей. Прежде всего,
они чувствительны к степени исходной упорядоченности массива. Полностью упорядо-
ченный массив будет просмотрен ими только один раз.

      Шейкер-сортировка учитывает тот факт, что от последней перестановки до конца
массива будут находиться уже упорядоченные данные. Исходя из этого утверждения,
просмотр имеет смысл делать не до конца массива, а до последней перестановки, вы-
полненной на предыдущем просмотре. Для этой цели в программе обменной сортировки
необходимо запоминать индекс переставляемой пары, который по завершении внутрен-
него цикла просмотра и будет индексом последней перестановки. Кроме того, необхо-
дима переменная - граница упорядоченной части, которая должна при переходе к сле-
дующему шагу получать значение индекса последней перестановки. Условие окончания
- граница сместится к началу массива.

void sort_sheyker(int A[], int n)
{                                // b граница отсортированной части
        int i, b, b1;            // b1 место последней перестановки
        for (b=n-1; b!=0; b=b1) // Пока граница не сместится к правому краю
        {
                 b1=0;
                 for (i=0; i A[i+1]) // Перестановка с запоминанием места
                         {
                                 int buf = A[i];
                                 A[i]=A[i+1];
                                 A[i+1]=buf;
                                 b1=i;
}      }                 }

                                               48