Быстрая сортировка на С

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

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

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

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

 

Вот собственно вся функция сортировки массива целых чисел(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);
}

dreamway89

dreamway89 wrote 29 posts

Post navigation


Добавить комментарий

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>