4.3 Коды для быстрого поиска (функции 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