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

Быстрая сортировка, сортировка Хоара (англ.quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

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

Вот собственно вся функция сортировки массива целых чисел(int):

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quick_sort(int *s_arr, int first, int last)
{
	int i = first, j = last, x = s_arr[(first + last)/2];

	do {
		while(s_arr[i] < x) i++; while(s_arr[j] > x) j--;

		if(i <= j) { if(s_arr[i] > s_arr[j])
				swap(&s_arr[i], &s_arr[j]);
			i++;
			j--;
		}
	} while(i <= j);

	if(i < last)
		quick_sort(s_arr, i, last);
	if(first < j)
		quick_sort(s_arr, first, j);
}