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])) 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;

4.4 Коды для стандартной реализации быстрого поиска

#include <limits.h>

#define MAXSTACK (sizeof(size t) * CHAR BIT)

static void exchange(void *a, void *b, size t size) { size t i;

/******************

* exchange a,b * ******************/

for (i = sizeof(int); i <= size; i += sizeof(int)) {

int t = *((int *)a); *(((int *)a)++) = *((int *)b); *(((int *)b)++) = t;

for (i = i - sizeof(int) + 1; i <= size; i++) { char t = *((char *)a);

*(((char *)a)++) = *((char *)b); *(((char *)b)++) = t;

void qsort(void *base, size t nmemb, size t size,

int (*compar)(const void *, const void *)) {

void *lbStack[MAXSTACK], *ubStack[MAXSTACK];

int sp;

unsigned intoffset;

lbStack[0] =(char *)base;

ubStack[0] =(char *)base + (nmemb-1)*size;

for (sp = 0;sp >= 0; sp-- ) { char *lb, *ub, *m;

char *P,*i, *j;

lb = lbStack[sp]; ub = ubStack[sp];

while (lb < ub) {

/* select pivot and exchange with 1st element */

offset = (ub - lb) >> 1;

P = lb + offset - offset % size; exchange (lb, P, size);

/* partition into two segments */ i = lb + size;

j = ub; while (1) {

while (i < j && compar(lb, i) > 0) i + while (j >= i && compar(j, lb) > 0) j if (i >= j) break;

= size; -= size;