4.3 Коды для быстрого поиска (функции Quicksort)

typedef int T; /* type of item to be sorted */

typedef int tbllndex;      /* type of subscript */

#define CompGT(a,b)   (a > b)

tbllndex partition(T *a,  tbllndex lb,  tbllndex ub) { T t, pivot; tbllndex 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])) while   (j >= i && compGT(a[j], pivot)) j--; if  (i >= j) break;

t = a[i];

a[i] = a[j];

a[j] = t;

}

/* pivot belongs in a[j] */

a[lb] = a[j];

a[j] = pivot;

return j;

}

void quickSort(T *a,  tbllndex lb,  tbllndex ub) { tbllndex 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;

}

}