Ñîðòèðîâêà è ïîèñê - ðåöåïòóðíûé ñïðàâî÷íèê

       

Êîäû äëÿ ñòàíäàðòíîé ðåàëèçàöèè áûñòðîãî ïîèñêà


 

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

            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 += size;

                while (j >= i && compar(j, lb) > 0) j -= size;

                if (i >= j) break;

                exchange (i, j, size);

                j -= size;

                i += size;

            }

 

            /* pivot belongs in A[j] */

            exchange (lb, j, size);

            m = j;

 

            /* keep processing smallest segment, and stack largest */

            if (m - lb <= ub - m) {

                if (m + size < ub) {

                    lbStack[sp] = m + size;

                    ubStack[sp++] = ub;

                }

                ub = m - size;

            } else {

                if (m - size > lb) {

                    lbStack[sp] = lb;

                    ubStack[sp++] = m - size;

                }

                lb = m + size;

            }

        }

    }

}



Ñîäåðæàíèå ðàçäåëà