3.3. Быстрая сортировка Хоара (сортировка разделением)
 

Этот метод является усовершенствованием метода, основанного на обмене. Несмотря на то, что пузырьковая сортировка является наименее эффективной из трех прямых методов сортировки, метод быстрой сортировки оказался самым лучшим известных в настоящее время методов. Он заключается в следующем. Выбираем наугад какой-либо элемент х исходного массива. Будем просматривать слева наш массив до тех пор, пока не встретим элемент а_i > х, затем будем просматривать массив справа пока не встретим а_j ≤ х. Поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена до тех пор, пока оба просмотра не встретятся. В результате исходный массив окажется разбитым на две части, левая часть будет содержать элементы меньше или равные х, а правая часть — элементы больше х. Применив эту процедуру разделения к левой и правой частям массива от точки встречи, получим четыре части и т.д., пока в каждой части окажется только один элемент.

Остается решить вопрос, каким образом выбирать граничный элемент х для разделения. Если при равновероятном распределении элементов массива в качестве разделения каждый раз выбирать медиану, то общее число сравнений будет равно n*\log₂n, а общее число обменов — (n*log₂n)/6. При случайном выборе границы средние затраты увеличатся всего лишь в (2*ln ₂) раза. Однако при крайне неблагоприятном случае, когда каждый раз для разделения выбирается наибольший элемент в обрабатываемой части массива, производительность процедуры будет наихудшая, порядка 0(n2). Обычно в процедурах быстрой сортировки в качестве границы выбирают средний элемент, при этом получаются неплохие показатели производительности.

Рассмотрим пример сортировки посредством рекурсивной функции.
Пример.
/'БЫСТРАЯ СОРТИРОВКА ХОАРА */
#include <stdio.h>
#define n 15
int A[n]={12,2,13,4,15,6,9,11,3,7,5,10,1,8,14};
/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =*/
main()
{ void QuickSort(int A[],int L,int R);
int j;
printf("\n Исходный массив: \n\t\t");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf("\n Отладочная печать");
QuickSort(A,0,n-1);
printf("\n Отсортированный массив :\п");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf("\n"); getch(); return 0;
}
/* РЕКУРСИВНАЯ ФУНКЦИЯ БЫСТРОЙ СОРТИРОВКИ */
void QuickSort(int A[],int L,int R)
{ int i,j,k,x,m;
i=L; j=R;
x=A[(L+R)/2];
do {
while (A[i]<x)
i++;
while (x<A[j])
j--;
if(i≤j)
{ k=A[i]; A[i]=A[j]; A[j]=k;
i++; j--;
/* Отладочная печать */
printf("\n i=%d j=%d x=%d: ",i-1,j+1,x);
for (m=0; m<n; m++)
printf(" %d”,A[m]);
}
}
while (i<j);
if (L<j)
{ printf("\t L=%d j=%d",L,j);
QuickSort(A,L,j);
}
if (i{ printf("\t i=%d R=%d",i,R);
QuickSort(A,i,R);
}
}
Исходный массив:
12 2 13 4 15 6 9 11 3 7 5 10 1 8 14.
Отладочная печать:
I=0 j=13 x=11: 8 2 13 4 15 6 9 11 3 7 5 10 1 12 14
I=2 j=12 x=11: 8 2 1 4 15 6 9 11 3 7 5 10 13 12 14
I=4 j=11 x=11: 8 2 1 4 10 6 9 11 3 7 5 15 13 12 14
I=7 j=10 x=11: 8 2 1 4 10 6 9 5 3 7 11 15 13 12 14 L=0 j=9
I=4 j=9 x=10: 8 2 1 4 7 6 9 5 3 10 11 15 13 12 14 L=0 j=8
I=0 j=9 x=7 : 3 2 1 4 7 6 9 5 8 10 11 15 13 12 14
I=4 j=7 x=7 : 3 2 1 4 5 6 9 7 8 10 11 15 13 12 14 L=0 j=5
I=0 j=2 x=1 : 1 2 3 4 5 6 9 7 8 10 11 15 13 12 14 L=0 j=1
I=0 j=0 x=1 : 1 2 3 4 5 6 9 7 8 10 11 15 13 12 14 I=1 R=5
I=3 j=3 x=4 : 1 2 3 4 5 6 9 7 8 10 11 15 13 12 14 L=1 j=2
I=1 j=1 x=2 : 1 2 3 4 5 6 9 7 8 10 11 15 13 12 14 I=4 R=5
I=4 j=4 x=5 : 1 2 3 4 5 6 9 7 8 10 11 15 13 12 14 I=6 R=8
I=6 j=7 x=7 : 1 2 3 4 5 6 7 9 8 10 11 15 13 12 14 I=7 R=8
I=7 j=8 x=9 : 1 2 3 4 5 6 7 8 9 10 11 15 13 12 14 I=10 R14
I=11 j=13 x=13: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 L=10 j=12
I=11 j=11 x=12: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 I=12 R14
I=13 j=14 x=15: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 L=12 j=13
I=12 j=12 x=13: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Алгоритм быстрой сортировки можно реализовать и в виде нерекурсивной функции. При этом рекурсия заменяется итерацией, естественно, понадобятся дополнительные операции в функции по сохранению нужной информации в стеке. На каждом этапе разделения, как было показано, возникают, в свою очередь, две задачи по разделению. Одну из них мы можем выполнять сразу в очередной операции, а информацию о второй придется запоминать в перечне разделений (в стеке), которые необходимо провести позже. Каждое требование на разделение задается просто левой и правой границами — индексами массива и заносится в стек, организованный в виде массива структур. Требования из стека выполняются в обратном порядке. Максимальный размер стека равен n (размер исходного массива), однако эта граница, как правило, не достигается. Ниже приводится пример использования нерекурсивной функции быстрой сортировки NRQuickSort.
Пример.
/'НЕРЕКУРСИВНАЯ ФУНКЦИЯ БЫСТРОЙ СОРТИРОВКИ ХОАРА 7
#include <stdio.h>
#define n 15
int A[n]={12,2,13,4,15,6,9,11,3,7,5,10,1,8,14};
main()
{ void NRQuickSort(int A[],int nn);
int j;
printf("\n Исходный массив: \n\t\t");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf(“\n Отладочная печать”);
for (j=0;j<n;j++)
printf (“%d”,A[j]);
printf (“\n”);
getch(); return 0;
}
/* Нерекурсивная функция быстрой сортировки */
void NRQuickSort(int A[],int nn)
{
int I,j,k,x,m,s,L,R;
#define d 16
struct stack
{ int L; int R;} st[d];
s=1;st[1].L=0;st[1].R=nn-1;
do {
L=st[s].L; R=st[s].R;s--;
do
{I=L; j=R;
x=A[(L+R)/2];
do
{ while (A[I]<x) I++;
while (x<a[j])j--;
if (I≤j)
{ k=A[I]; A[I]=A[j]; A[j]=k
I++; j--;
/* Отладочная печать */
printf(“\n I=%d j=%d x=%d:”,I-1,j+1,x);
for (m=0;m<n;m++)
printf(“%d”,A[m]);
}
}
while (I<j);
if (I<R)
{
s++;st[s].L=I; st[s].R=R;
printf(“I=%d R=%d s=%d”,I,R,s);
}
R=j;
}
while (L<R);
}
while (a!=R);
}