Сортировка Хоара это третий, и думаю последний, метод относящийся к обменным сортировкам. Этот метод метод признан одним из лучших методов сортировки, которые когда-либо придумали. Он даже носит название "Быстрой сортировки".

В методе Хоара первоначально выделяют базовый элемент, относительно которого ключи с большим весом перебрасываются вправо, а с меньшим влево. Базовый элемент сравнивается с противоположным элементом.

В качестве базового элемента очень удобно брать крайние элементы.

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

Дано множество
{9,6,3,4,10,8,2,7}

Берем 9 в качестве базового элемента. Сравниваем 9 с противоположностоящим элементом, в данном случае это 7. 7 меньше, чем 9, следовательно элементы меняются местами.

{7,6,3,4,10,8,2,9}

Далее начинаем последовательно сравнивать элементы с 9, и менять их местами в зависимости от сравнения.

{7,6,3,4,10,8,2,9}
{7,6,3,4,10,8,2,9}
{7,6,3,4,10,8,2,9}
{7,6,3,4,9,8,2,10} - 9 и 10 меняем местами.
{7,6,3,4,8,9,2,10} - 9 и 8 меняем местами.
{7,6,3,4,8,2,9,10} - 2 и 9 меняем местами.

После такого перебрасывания элементов весь массив разбивается на два подмножетсва, разделенных элементом 9.

{7,6,3,4,8,2}
{10}

Далее по уже отработанному алгоритму сортируются эти подмножества. Подмножество из одного элемента естественно можно не сортировать. Выбираем в первом подмножестве базовый элемент 7.

{7,6,3,4,8,2}

{2,6,3,4,8,7} - меняем местами 2 и 7.
{2,6,3,4,8,7}
{2,6,3,4,8,7}
{2,6,3,4,8,7}
{2,6,3,4,7,8}- меняем местами 7 и 8

Получили снова два подмножества.

{2,6,3,4}
{8}

А дальше все происходит аналогично... В результате можно родить такую программу %) :

int QuickSort(int *array, int left, int right)
{
	long base, opposite, p;
	int c;
	base=left;
	opposite=right;
	while (base!=opposite){
		if ((array[base]>array[opposite])^(base>opposite)){

			c=array[base];
			array[base]=array[opposite];
			array[opposite]=c;

			p=base;
			base=opposite;
			if (p<opposite)
				opposite=p+1; else opposite=p-1;
		} else {
			if (base<opposite)
				opposite--; else opposite++;
		};
	};

	if (left<base-1) QuickSort(array,left,base-1);
	if (base+1<right) QuickSort(array,base+1,right);
};

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