Сортування й пошук: Рецептурний довідник, страница 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;

    }

}

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;

    }

}

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;

        }

    }

}

#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;