allsort.h

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

    ps[pcount].start = 0;
    ps[pcount].ascending = GE(array[1], array[0]);
    for (i = 1; i < n; i++) {
        direction = GE(array[i], array[i - 1]);
        if (ps[pcount].ascending != direction) {
            ps[pcount].end = i - 1;
            pcount++;
            if (pcount > max_par)
                return -max_par;
            ps[pcount].start = i;
            if (i == n - 1)
                ps[pcount].ascending = 1;
            else
                ps[pcount].ascending = GE(array[i + 1], array[i]);
        }
    }
    ps[pcount].end = n - 1;
    pcount++;
    return pcount;
}

/*
** Remove the smallest item from a partition.
*/
PRELUDE
Etype PDELETEMIN(partition * p, char *end, Etype data[])
{
    Etype           e;
    if (p->start < p->end) {
        *end = 0;
    } else {
        *end = 1;
        if (p->start > p->end)
            puts("Error! Deletion from empty partition");
    }
    if (p->ascending) {
        e = data[p->start++];
    } else {
        e = data[p->end--];
    }

    return e;
}

/*
** Retrieve the smallest item from a partition.
*/
PRELUDE
Etype PGETMIN(partition p, Etype data[])
{
    Etype           e;
    if (p.ascending) {
        e = data[p.start];
    } else {
        e = data[p.end];
    }
    return e;
}

/*
** This shell-sort operates on partitions of data, rather
** than on simple data elements.
*/
PRELUDE
void            PSHELLSORT(partition array[], size_t count, Etype * data)
{
    size_t          i,
                    inc,
                    j;

    partition       tmp;
    Etype           etmp;

    for (inc = count; inc > 0;) {
        for (i = inc; i < count; i++) {
            j = i;
            tmp = array[i];
            etmp = PGETMIN(tmp, data);
            while (j >= inc && (LT(etmp, PGETMIN(array[j - inc], data)))) {
                array[j] = array[j - inc];
                j -= inc;
            }
            array[j] = tmp;
        }                       /* Calculate the next h-increment */
        inc = (size_t) ((inc > 1) && (inc < 5)) ? 1 : 5 * inc / 11;
    }
}

/* Normalize a partition by removing the first item
** or changing its precedence and moving to the right
** location.
*/
PRELUDE
void            PNORMALIZE(partition * array, size_t count, Etype data[])
{
    long            beg;        /* Search beginning here (this moves toward
                                 * ipg) */
    long            ipg;        /* Current guess for the insertion point */
    long            end;        /* Search ending here (this moves toward ipg) */
    partition       temp;       /* Hold one partition in temporary storage */
    long            i;

    Etype           McGuffin = PGETMIN(array[0], data);
    /* Maybe we don't need to do anything (I'm an optimist) */
    if (count < 2 || LE(McGuffin, PGETMIN(array[1], data)))
        return;

    /* inline binary search to find point of insertion */
    beg = ipg = 1;              /* The first element of the ordered part of
                                 * the data is element 0 */
    end = count - 1;            /* The last element already ordered is
                                 * element partition */
    /* Without this check, loop terminates only if an equal element is
     * already sorted */
    while (end >= beg) {
        /* insertion point guess of halfway between beginning and ending */
        ipg = ((end + beg) >> 1);
        if (GE(PGETMIN(array[ipg], data), McGuffin))
            end = ipg - 1;
        else
            beg = ++ipg;
    }
    /* make room at data[ipg] for data[0] */
    temp = array[0];            /* Save the new element we are ready to
                                 * insert */
    for (i = 0; i < ipg; i++)
        array[i] = array[i + 1];
    array[ipg - 1] = temp;      /* Put the new element in its sorted order */
    return;
}

/*
Most significant digit radix sort.
The outline of these sorts comes from "Algorithms in C"
by Robert Sedgewick, ISBN:0-201-31452-5.

I have added a generic CHUNK operator.  This operator
is analogous to the compare operator for a standard sort.
Besides just peeling out the digit, CHUNK performs whatever
transforation is needed in order to put the bits in the
proper order of significance.
*/
#ifndef RADIX_MISSING

#define bin(A) l+count[A]

PRELUDE
void            RADIXMSD(Etype a[], long l, long r, unsigned w)
{
    if (w > KEYSIZE || r <= l)
        return;
    if (r - l <= LargeCutoff * COST) {
        IQSORT5(a + l, r - l + 1);
        return;
    } else {
        long            i,
                        j,
                        count[R + 1] = {0};
        Etype          *b = malloc((r - l + 1) * sizeof(Etype));

        /* Use standard comparison sort if allocation fails */
        if (b == NULL) {
            IQSORT5(a + l, r - l + 1);
            return;
        }
        /* increment the starting place for the next bin */
        for (i = l; i <= r; i++) {
            count[CHUNK(a + i, w) + 1]++;
        }

        /* Add the previous bin counts to find true offset */
        for (j = 1; j < R; j++)
            count[j] += count[j - 1];

        /* Distribute according to bin positions */
        for (i = l; i <= r; i++) {
            b[count[CHUNK(a + i, w)]++] = a[i];
        }
        /* Transfer back to the original array */
        for (i = l; i <= r; i++)
            a[i] = b[i - l];
        free(b);

        /* Process the next chunk of the key for the first bin */
        RADIXMSD(a, l, bin(0) - 1, w + 1);
        for (j = 0; j < R - 1; j++) {
            /* Process the next chunk of the key for the rest of the  bins */
            RADIXMSD(a, bin(j), bin(j + 1) - 1, w + 1);
        }

    }
}
/*
Least significant digit radix sort.
The outline of these sorts comes from "Algorithms in C"
by Robert Sedgewick, ISBN:0-201-31452-5.

I have added a generic CHUNK operator.  This operator
is analogous to the compare operator for a standard sort.
Besides just peeling out the digit, CHUNK performs whatever
transforation is needed in order to put the bits in the
proper order of significance.
There is also a CHUNKS operator that finds all single chunks
in the data object at once.
*/
PRELUDE
void            RADIXLSD(Etype a[], long l, long r, size_t keysize)
{
    int             i,
                    j,
                    w;
    Etype          *b;

    if (r - l <= LargeCutoff * COST) {
        IQSORT5(a + l, r - l + 1);
        return;
    }
    /* For long keys, LSD Radix sort is too expensive */
    if (KEYSIZE > 8) {
        RADIXMSD(a, l, r, 0);
        return;
    } else {
        unsigned long   cnts[R + 1][8] = {0};
        b = malloc((r - l + 1) * sizeof(Etype));

        /* Use standard comparison sort if allocation fails */
        if (b == NULL) {
            IQSORT5(a + l, r - l + 1);
            return;
        }
        /* Count the bins all at once */
        for (i = l; i <= r; i++)
            CHUNKS(a + i, cnts);
        for (w = KEYSIZE - 1; w >= 0; w--)
            /* Add the previous bin counts to find true offset */
            for (j = 1; j < R; j++)
                cnts[j][w] += cnts[j - 1][w];


        for (w = KEYSIZE - 1; w >= 0; w--) {
            long            count[R + 1] =
            {0};

            /* Distribute according to bin positions */
            for (i = l; i <= r; i++) {
                b[cnts[CHUNK(&a[i], w)][w]++] = a[i];
            }
            /* Transfer back to the original array */
            for (i = l; i <= r; i++)
                a[i] = b[i];
        }
        free(b);
    }
}
#endif


/*
** This merge sort is *almost* actually useful.
** The file I/O based version does have a real purpose.
** This one is just for fun.  Don't bother with it.
** quick-sort beats it hands-down and does not need extra memory.
*/
PRELUDE
void            MERGE_SORT(Etype a[], unsigned long count, partition * pset, unsigned long max_par)
{
    long            pcount;
    Etype          *alternate = NULL;
    unsigned long   current = 0;
    unsigned long   increment = 0;

    /*
    ** -- PURE DISCOVERY of partitions --
    */
    pcount = PARSCAN(a, count, pset, max_par);
    /* If too many partitions by discovery, we use a cookie cutter to make
     * them. */
    /*
    ** -- COOKIE CUTTER if we ran out of partitions --
    */
    if (pcount < 0) {
        unsigned long   j;
        increment = count / (max_par) + 1;
        if (increment < SmallCutoff)
            increment = SmallCutoff;
        for (j = 0; j < count; j += increment)
            IQSORT5(&a[j], increment);
        if (count % increment)
            IQSORT5(&a[count - (count % increment)], count % increment);
        /*
        ** This is actually pretty lazy of me.  But this routine is
        ** just a toy anyway.  The real partition merge-sort is elsewhere.
        */
        pcount = PARSCAN(a, count, pset, max_par);

    }
    /*
    ** If we have a single partition we can save some time
    */
    if (pcount == 1) {
        if (pset[0].ascending)
            return;
        else {
            REVERSEARRAY(a, pset[0].start, pset[0].end);
            return;
        }
    }
    /*
    ** One great weakness of many merge sort routines -- memory hogs.
    */
    if ((alternate = malloc(count * sizeof(Etype)))) {
        /* After this step, all partitions will be ordered from smallest to
         * largest */
        PSHELLSORT(pset, pcount, a);
        {
            char            end = 0;
            Etype           e;
            while (current < count) {
                e = PDELETEMIN(pset, &end, a);
                alternate[current++] = e;

                if (end) {
                    pset++;
                    pcount--;
                } else {
                    PNORMALIZE(pset, pcount, a);
                }
            }
        }
        memcpy(a, alternate, count * sizeof(Etype));
        free(alternate);
    } else /* So much for stable.  But what if malloc() fails? */
        IQSORT5(a, count);
}
/*
** The following routines are for a horrible but easily understandable
** form of merge-sort.   Here, we actually join the ordered data
*/
PRELUDE
void            MMERGE(Etype A[], Etype B[], size_t l, size_t m, size_t r)
{
    size_t          i = l;
    size_t          j = m + 1;
    size_t          k = l;
    /* Put the smallest thing into array B */
    while ((i <= m) && (j <= r)) {
        if (LT(A[i], A[j]))
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    }
    /* Copy leftover (if any) */
    while (i <= m) {
        B[k++] = A[i++];
    }
    while (j <= r) {
        B[k++] = A[j++];
    }
    /* Transfer back to original array */
    for (k = l; k <= r; k++) {
        A[k] = B[k];
    }
}

/* Helper function for icky(tm) merge sort */
PRELUDE
void            MSORT(Etype A[], Etype B[], size_t l, size_t r)
{
    size_t          m;          /* The middle */
    if (l < r) {                /* Cut problem to half size until 1 unit */
        /* Divide partition by 2, sort and merge */
        m = ((l + r) >> 1);
        MSORT(A, B, l, m);
        MSORT(A, B, m + 1, r);
        MMERGE(A, B, l, m, r);  /* A single element is ordered */
    }
}
/*
This is a really bad merge sort.  Please don't use it.
It is for educational purposes only.
*/
PRELUDE
void            MERGESORTB(Etype A[], size_t count)
{
    Etype          *B;
    if ((B = malloc(count * sizeof(Etype)))) {
        MSORT(A, B, 0, count - 1);
        free(B);
    } else                      /* Hopefully, we will fail and use a good
                                 * sort. ;-) */
        IQSORT5(A, count);
}