Продолжаю записи про язык программирования С, точней про различные структуры и простейшие алгоритмы. Следующей в очереди идет быстрая сортировка, вот что о ней пишут в википедии:
Быстрая сортировка, сортировка Хоара (англ.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); }