Шаблон функции быстрой сортировки
Приведем пример реализации вышеупомянутого рекурсивного алгоритма сортировки массива переменных Quicksort. Его идея состоит в том, что меняются местами элементы массива, стоящие слева и справа от выбранного "центрального" (mid) элемента массива, если они нарушают порядок последовательности. Интервал, в котором выбирается центральный элемент, постепенно сжимается, "расправляясь" сначала с левой половиной массива, затем с правой. Функция Quicksort, приведенная ниже, реализует рекурсивный алгоритм быстрой сортировки. Далее следует код, который позволяет протестировать работу функции. Сортируется массив вещественных чисел, элементы которого заданы случайным образом:
void Quicksort (double *ar, int 1, int r)
{
//========== Рабочие переменные
double mid, temp;
//========== Левая и правая границы интервала
int i = 1, j = r;
//========== Центральный элемент
mid = ar[ (1 + r) /2];
//========== Цикл, сжимающий интервал
do
//== Поиск индексов элементов, нарушающих порядок
while (ar[i] < mid)
i++; // слева
while (mid < ar[j])
j--; // и справа
//== Если последовательность нарушена,
if (i <= j)
{
//===== то производим обмен
temp = ar[i];
ar[i++] = ar[j];
ar[j-– ] = temp;
}
}
//========= Цикл do-while повторяется, пока
//========= есть нарушения последовательности
while (i <= j);
//========= Если левая часть не упорядочена,
if (I < j)
Quicksort (ar, 1, j); // то занимаемся ею
// Если правая часть не упорядочена,
if (i < r)
Quicksort (ar, i, r); // то занимаемся ею }
//========== Тестируем алгоритм
void main()
{
//========= Размер массива сортируемых чисел
const int N = 21;
double ar[N]; // Сам массив
puts ("\n\nArray before Sorting\n");
for (int i=0; i<N; i++)
{
ar[i] = rand()%20;
if (i%3==0)
printf ("\n");
printf ("ar[%d]=%2.0f\t",i,ar[ij);
}
Quicksort(ar,0,N-1); // Сортировка
puts ("\n\nAfter SortingNn");
for (i=0; i<N; i++)
{
if (i%3==0)
printf ("\n");
printf ("ar[%d]=%2.0f\t",i,ar[i]);
}
puts ("\n");
}