allsort.h

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

   if (ARRAYISREVERSED(array, 0, count-1)) {
     REVERSEARRAY(array, 0, count-1);
     return;
   }
 */
        for (partition = 1; partition < count; partition++) {
            /* inline binary search to find point of insertion */
            beg = ipg = 0;      /* The first element of the ordered part of
                                 * the array is element 0 */
            end = partition - 1;/* The last element already ordered is
                                 * element partition-1 */

            /* 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);       /* BUGBUG: we can't sort sets
                                                 * > (MAX_LONG)/2 elements */
                /* However, this sort should *NEVER* be used for anything but
                 * tiny partitions */

                /* The element sitting at the end of the partition is the one
                 * we will insert */
                /* It is not ordered yet, but all the array to the left of it
                 * is in sort. */
                if (GT(array[ipg], array[partition]))
                    end = ipg - 1;
                else
                    beg = ++ipg;
            }
            /* make room at array[ipg] for array[i] */
            /* It might already be in the right place */
            if (partition != (unsigned long) ipg) {
                temp = array[partition];        /* Save the new element we
                                                 * are ready to insert */
                /* Move the data from the insertion point downward.  We can't
                ** use memcpy()!
                ** For C++, you will have to replace this because memmove
                ** does not fire constructors!  Shell-sort is better anyway.
                */
                memmove(&array[ipg + 1], &array[ipg], (partition - ipg) * sizeof(Etype));
                array[ipg] = temp;      /* Put the new element in its sorted
                                         * order */
            }
        }

    }
    return;
}

/*
** The h-constants for this version of Shell-sort come from:
** Handbook of Algorithms and Data Structures in Pascal and C
** By Gaston Gonnet, Ricardo Baeza-Yates
** Addison Wesley; ISBN: 0201416077
** These h-increments work better for me than Sedgewick's under
** full optimization.  Your mileage may vary, so I suggest you
** try Sedgewick's suggestions as well.  The h-increment arena
** is a rich environment for exploration.  I suggest attempting
** all possible permutations below 20, since that is where a
** good shell-sort is crucuial.  If you find something wonderul
** you may get your name up in lights.
*/
PRELUDE
void            SHELLSORT(Etype array[], size_t count)
{
    size_t          i,
                    inc,
                    j;
    Etype           tmp;

    switch (count) {
    case 0:
    case 1:
        return;
    case 2:
        INSERTTWO(array);
        return;
    case 3:
        INSERTTHREE(array);
        return;
    case 4:
        INSERTFOUR(array);
        return;
#ifdef MY_CACHE_IS_ENORMOUS
    case 5:
        InsertFive(array);
        return;
#endif

    default:

        for (inc = count; inc > 0;) {
            for (i = inc; i < count; i++) {
                j = i;
                tmp = array[i];
                while (j >= inc && (LT(tmp, array[j - inc]))) {
                    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;
        }
    }
}

/* Test to see if segment [Lo, ... Hi] is sorted already */
PRELUDE
long            ARRAYISSORTED(Etype A[], unsigned long Lo, unsigned long Hi)
{
    unsigned long   i;
    unsigned int    ascending;
    if (Lo == Hi)
        return 1;
    if ((ascending = (LE(A[Lo], A[Lo + 1]))))
        for (i = Lo + 1; i < Hi; i++) {
            /* Is the next item bigger than this one? */
            if (GT(A[i], A[i + 1])) {
                /* Were all of them the same size up to here? */
                if (EQ(A[i], A[Lo]))
                    /* Maybe the partition is reversed? */
                    if (ARRAYISREVERSED(A, i, Hi)) {
                        /* It was reversed.  Invert it and we are done! */
                        REVERSEARRAY(A, Lo, Hi);
                        return 1;
                    } else {    /* Nope.  The partition is not reversed */
                        return 0;
                    }
                else
                    return 0;
            }
        }
    /* not ascending */
    else if (ARRAYISREVERSED(A, Lo, Hi)) {
        /* It was reversed.  Invert it and we are done! */
        REVERSEARRAY(A, Lo, Hi);
        return 1;
    } else
        return 0;
    return 1;
}

/* Test to see if segment [Lo, ... Hi] is reverse sorted already */
PRELUDE
long            ARRAYISREVERSED(Etype A[], unsigned long Lo, unsigned long Hi)
{
    unsigned long   i;
    for (i = Lo; i < Hi; i++) {
        if (LE(A[i], A[i + 1]))
            return 0;
    }
    return 1;
}
/*
Reverse the order of a partition.
*/
PRELUDE
void            REVERSEARRAY(Etype * A, unsigned long Lo, unsigned long Hi)
{
    Etype          *r = A + Lo;
    for (r = A + (Hi - Lo); A < r; A++, r--) {
        Etype           Tmp = *A;
        *A = *r;
        *r = Tmp;
    }
}

/*
Primitive quicksort.  This is a bad algorithm for general purposes.
Don't use it.  Use IQSORT5 instead.  This thing is a bomb waiting to go off.
*/
PRELUDE
void            QSORTB(Etype * A, int l, int r)
{
    int             loc;

    if (l < r) {
        int             i = l,
                        j = r;
        Etype           tmp,
                        pivot = A[l];
        /* Divide piles into partitions */
        for (;;) {
            while ((GE(A[j], pivot)) && (j > l))
                j--;
            while ((LT(A[i], pivot)) && (i < r))
                i++;
            if (i < j) {
                tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            } else {
                loc = j;
                break;
            }
        }
        /* Recurse */
        QSORTB(A, l, loc);
        QSORTB(A, loc + 1, r);
    }
}


/*
Find the median of 3, with a bit of stirring.
*/
PRELUDE
void            MEDIAN(Etype A[], unsigned long n)
{
    unsigned long   m,
                    x,
                    i,
                    j,
                    k;
    Etype           t;
    i = (mtrand() + 1) % n;     /* We randomly stir the pot up a bit... */
    j = (mtrand() + 1) % n;     /* We randomly stir the pot up a bit... */
    k = n / 2;                  /* The middle element of a partition is a
                                 * good guess */
    /* Pick the center of these three */
    if (LE(A[i], A[j])) {
        if (LE(A[j], A[k])) {
            m = j;
            x = k;
        } else if (LE(A[i], A[k])) {
            m = k;
            x = j;
        } else {
            m = i;
            x = j;
        }
    } else {
        if (LE(A[i], A[k])) {
            m = i;
            x = k;
        } else if (LE(A[j], A[k])) {
            m = k;
            x = i;
        } else {
            m = j;
            x = i;
        }
    }
    /* Store out of the way... */
    t = A[0];
    A[0] = A[m];
    A[m] = t;
    t = A[n - 1];
    A[n - 1] = A[x];
    A[x] = t;
}

/*
Singleton's sorting algorithm.  ACM Algorithm 347 is due
to Richard Singleton.  The general outline I use was shown
to me by Dan Stubbs, and seems to work better than others
I have tried.  The test for an in-order partition was a
particularly good idea that he suggested.  The reverse check
and partition reversal was my idea.  Also, I use shell-sort
instead of insertion sort.  It is always better for a broad
variety of distributions, according to my tests. YMMV.
*/
PRELUDE
void            IQSORT5(Etype A[], unsigned long n)
{
    unsigned long   i,
                    j;
    Etype           t;
    /* Change algorithm for small partitions */
    if (n < SmallCutoff) {
        SHELLSORT(A, n);
        return;
    }
    /* Check for preordered array: * The idea to check for a presorted array
     * came * to me from Dan Stubbs [[e-mail]].  If the
     * partition is already ordered, then we are done.  I added a second
     * check for a reversed partition.  If the * partition is reversed, I
     * reverse it and we are done. */
    if (ARRAYISSORTED(A, 0, n - 1))
        return;

    /* Stir up the data a bit, and pick a median estimate. */
    MEDIAN(A, n);

    i = 0;
    j = n;
    /* Form partitions */
    for (;;) {
        do
            i++;
        while (LT(A[i], A[0]) && i < n);
        do
            j--;
        while (GT(A[j], A[0]) && j > 0);
        if (j < i)
            break;
        t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
    /* Restore pivot */
    t = A[0];
    A[0] = A[j];
    A[j] = t;

    /* Recurse smaller partition first */
    if (j < n - j) {
        IQSORT5(A, j);
        IQSORT5(A + j + 1, n - j - 1);
    } else {
        IQSORT5(A + j + 1, n - j - 1);
        IQSORT5(A, j);
    }
}

/*
** Test to see if segment [Lo, ... Hi] is sorted already
** This one does not try to fix anything because it is for
** testing purposes only.
*/
PRELUDE
long            INSORT(Etype A[], unsigned long Hi)
{
    unsigned long   i;
    for (i = 0; i < Hi - 1; i++) {      /* Is the next item bigger than this
                                         * one? */
        if (GT(A[i], A[i + 1])) {
            return 0;
        }
    }
    return 1;
}

/*
This version of heapsort is adapted from:

Data Structures and Algorithm Analysis in C (Second Edition)
by Mark Allen Weiss
Addison-Wesley, 1997
ISBN: 0-201-49840-5
Page 228.

It is simple and interesting, but quick-sort is better than heap-sort.
*/

#define LeftChild( i )  ( 2 * ( i ) + 1 )

void            PERCDOWN(Etype A[], int i, int N)
{
    int             Child;
    Etype           Tmp;

    for (Tmp = A[i]; LeftChild(i) < N; i = Child) {
        Child = LeftChild(i);
        if (Child != N - 1 && GT(A[Child + 1], A[Child]))
            Child++;
        if (LT(Tmp, A[Child]))
            A[i] = A[Child];
        else
            break;
    }
    A[i] = Tmp;
}

void            HEAPSORT(Etype A[], int N)
{
    int             i;

    for (i = N / 2; i >= 0; i--)
        /* BuildHeap */
        PERCDOWN(A, i, N);
    for (i = N - 1; i > 0; i--) {
        SWAP(&A[0], &A[i]);
        /* DeleteMax */
        PERCDOWN(A, 0, i);
    }
}


/*
** The purpose of this routine is to discover partitions in the data.
** This is a two state FSM.
** Ascend = 1, Descend = 0.
**
** This is a vastly improved version of my ugly code.
** The large improvement was from Kang Su Gatlin.
**
*/
PRELUDE
int             PARSCAN(Etype * array, unsigned long n, partition ps[], long max_par)
{
    unsigned long   i;
    char            direction;
    long            pcount = 0;