Êîäû äëÿ áûñòðîãî ïîèñêà (ôóíêöèè Quicksort)
typedef int T; /* type of item to be sorted */
typedef int tblIndex; /* type of subscript */
#define CompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
T t, pivot;
tblIndex i, j, p;
/*******************************
* partition array a[lb..ub] *
*******************************/
/* select pivot and exchange with 1st element */
p = lb + ((ub - lb)>>1);
pivot = a[p];
a[p] = a[lb];
/* sort lb+1..ub based on pivot */
i = lb+1;
j = ub;
while (1) {
while (i < j && compGT(pivot, a[i])) i++;
while (j >= i && compGT(a[j], pivot)) j--;
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
j--; i++;
}
/* pivot belongs in a[j] */
a[lb] = a[j];
a[j] = pivot;
return j;
}
void quickSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex m;
/**************************
* sort array a[lb..ub] *
**************************/
while (lb < ub) {
/* quickly sort short lists */
if (ub - lb <= 12) {
insertSort(a, lb, ub);
return;
}
/* partition into two segments */
m = partition (a, lb, ub);
/* sort the smallest partition */
/* to minimize stack requirements */
if (m - lb <= ub - m) {
quickSort(a, lb, m - 1);
lb = m + 1;
} else {
quickSort(a, m + 1, ub);
ub = m - 1;
}
}
}
