Сортировка - это упорядочивание элементов по возрастанию или убыванию. Сортировка очень важная операция во всех сферах программирования.

Во всех обменных сортировках сравниваются два элемента отстоящие друг от друга на расстоянии d. При этом два элемента сравниваются и элемент с большим весом перемещается вправо, а с меньшим влево.

Стандартный обмен

Метод стандартного обмена еще называется "Методом Пузырька". В этом методе d=1, т.е. сравниваются рядом стоящие элементы. При первом проходе алгоритм последовательно сравнивает по два элемента и меняет их местами в зависимости от условия сортировки. При этом на последнем месте оказывается самый максимальный (минимальный) элемент. На втором шаге алгоритм сравнивает первые N-1 элементов в ставит предпоследним самый большой. При каждом последующем шаге интервал уменьшается на единицу.

Давайте рассмотрим пример:

Дано множество 
{8,3,4,2,5}

1. {3,8,4,2,5} - сравниваются 8 и 3, переставляются т.к. 8>3 
2. {3,4,8,2,5} - сравниваем 8 и 4, также переставляем.
3. {3,4,2,8,5}
4. {3,4,2,5,8} 

В результате этого первого шага элемент весом в 8, переместился в конец. Далее он не рассматривается и операция сортировки производится с множеством {3,4,2,5}.

В результате всех шагов у нас образуется отсортированное по возрастанию множество {2,3,4,5,8}.

А теперь программная реализация этого алгоритма.

#include <stdio.h>
#include <stdlib.h>

int BubbleSort(int *array,int len)
{
	int i,j,c;
	int k=0;
	for (i=len;i>1;i--)
	{
		k=0;
		for (j=1;j<i;j++)
		if (array[j]<array[j-1])
		{
			c=array[j];
			array[j]=array[j-1];
			array[j-1]=c;
			k=1;
		};
		if (k==0) return 0;
	};
};


int main()
{
	int k[6]={8,-5,1,7,3,-10};

	for (int i=0; i<6;i++)
		printf(" %d ",k[i]);
	printf("\n");

	BubbleSort(k,5);

	for (i=0; i<6;i++)
		printf(" %d ",k[i]);
	printf("\n");

	return 0;
};

Процедура BubbleSort() сортирует len первых элементов в массиве array.

Результат выполнения программы:

 8  -5  1  7  3  -10
 -5  1  3  7  8  -10

Наверно, Вы заметили, что элемент -10 не отсортировался. Это потому, что в сортировке участвовало 5 элементов.

Условия Айверсона

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

Условие:Сортировку можно прекратить досрочно, если на каком-то этапе в ходе сравнения не будет сделано ни одной перестановки.

За это условие в процедуре BubbleSort() отвечает переменная k, и условие if (k==0) return 0;.