# Сортування й пошук: Рецептурний довідник, страница 13

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

for (i = lb + 1; i <= ub; i++) {

t = a[i];

/* Shift elements down until */

/* insertion point found.    */

for (j = i-1; j >= lb && compGT(a[j], t); j--)

a[j+1] = a[j];

/* insert */

a[j+1] = t;

}

}

## 4.2     Коди для сортування Шелла

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

typedef int tblIndex;   /* type of subscript */

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

void shellSort(T *a, tblIndex lb, tblIndex ub) {

tblIndex n, h, i, j;

T t;

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

*  sort array a[lb..ub]  *

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

/* compute largest increment */

n = ub - lb + 1;

h = 1;

if (n < 14)

h = 1;

else if (sizeof(tblIndex) == 2 && n > 29524)

h = 3280;

else {

while (h < n) h = 3*h + 1;

h /= 3;

h /= 3;

}

while (h > 0) {

/* sort-by-insertion in increments of h */

for (i = lb + h; i <= ub; i++) {

t = a[i];

for (j = i-h; j >= lb && compGT(a[j], t); j -= h)

a[j+h] = a[j];

a[j+h] = t;

}

/* compute next increment */

h /= 3;

}

}

## 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 <= 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 int offset;

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;