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

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

Алгоритм можно улучшить с учетом того, что если в очередном проходе не было обмена, то последовательность упорядочена. Число сравнений в прямом обменном алгоритме C_m;n = n, С_mах = (n²-n)/2, число перестановок М_min = 0, М_средн = 3(n² - n)/4, М_mах = 3(n² - n)/2.
Пример.

/* СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА*/
#include
#include
#define n 8
int A[n]={27,412,71,81,59,14,273,87};
/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */
main()
{ void BblSort(int A[],int nn);
int j;
printf("\n Исходный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
BblSort(A,n);
printf("\n Отсортированный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
getch(); return 0;
}
/* ФУНКЦИЯ СОРТИРОВКИ МЕТОДОМ ПУЗЫРЬКА */
void BblSort(int A[],int nn)
{ int i,j,k,p;
for (i=0; i<nn—1; i++)
{ p=0;                               /* признак отсутствия обменов */
for (j=nn-1;j>i;j++)
  if (A[j]<A[j-1])
   {k=A[j];A[j]=A[j-1];A[j-1]=k;
      p=1;                                          /* был обмен */
}
/* Если обменов не было, то сортировка выполнена */
if (р== 0)
    return;
/* Отладочная печать по шагам сортировки */
printf (“\ni=%d",i);
for (j=0; j<nn;j++)
printf("\t %d”,A[j]);
}
}

Результаты выполнения программы:
Исходный массив:
27   412   71   81   59   14   273   87
Отладочная печать по шагам сортировки:
i=0   14  27  412  71  81  59  87  273
i=1   14  27  59  412  71  81  87  273
i=2   14  27  59  71  412  81  87  273
i=3   14  27  59  71  81  412  87  273
i=4   14  27  59  71  81  87  412  273
i=5    14  27  59  71  81  87  273  412

Отсортированный массив
14   27   59   71   81   87   273   412