allsort.h

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

/*
** The proper usage and copyright information for
** this software is covered in DSCRLic.TXT
** This code is Copyright 1999 by Dann Corbit
*/


/*
** This is a sort of "Poor-man's template for C" used to generate
** algorithms for sorting.
*/
#include <math.h>
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "mtrand.h"

/* This works best for ME.  YMMV. */

/* SmallCutoff is where the O(n*log(n)) sorts switch
** to an O(n^2) subfile sort.
*/
static const unsigned long SmallCutoff = 20;

/* LargeCutoff is where the O(n) sorts switch
** to O(n*log(n)) subfile sort
*/
static const unsigned long LargeCutoff = 200000;

/*
** If you are using C++, PRELUDE will define
** an inline function template.  The normal
** C version does nothing.  You may wish to make
** PRELUDE be static, so that you can use
** allsort.h as an include file in a normal C
** program.  The limitation is that when used this
** way, you can only sort one vector of a given
** type at a time.
*/
#define PRELUDE

/*
** Inteltyp.h contains definitions
** for radix sorting of Intel data types.
*/
#include "inteltyp.h"

/*
** By defininition of one of the following
** symbols, a routine (somewhat like a C++
** template) to define a sort for the named
** data type will be created.
*/
#if defined(ETYPE_UNSIGNED_INT)
#include "uicomp.h"
#elif defined(ETYPE_SIGNED_INT)
#include "sicomp.h"
#elif defined(ETYPE_UNSIGNED_LONG)
#include "ulcomp.h"
#elif defined(ETYPE_SIGNED_LONG)
#include "slcomp.h"
#elif defined(ETYPE_UNSIGNED_CHAR)
#include "uccomp.h"
#elif defined(ETYPE_SIGNED_CHAR)
#include "sccomp.h"
#elif defined(ETYPE_UNSIGNED_LONG_LONG)
#include "ullcomp.h"
#elif defined(ETYPE_SIGNED_LONG_LONG)
#include "sllcomp.h"
#elif defined(ETYPE_FLOAT)
#include "fcomp.h"
#elif defined(ETYPE_DOUBLE)
#include "dcomp.h"
#elif defined(ETYPE_LONG_DOUBLE)
#include "ldcomp.h"
#elif defined(ETYPE_P2_UNSIGNED_INT)
#include "puicomp.h"
#elif defined(ETYPE_P2_SIGNED_INT)
#include "psicomp.h"
#elif defined(ETYPE_P2_UNSIGNED_LONG)
#include "pulcomp.h"
#elif defined(ETYPE_P2_SIGNED_LONG)
#include "pslcomp.h"
#elif defined(ETYPE_P2_UNSIGNED_CHAR)
#include "puccomp.h"
#elif defined(ETYPE_P2_SIGNED_CHAR)
#include "psccomp.h"
#elif defined(ETYPE_P2_UNSIGNED_LONG_LONG)
#include "pullcomp.h"
#elif defined(ETYPE_P2_SIGNED_LONG_LONG)
#include "psllcomp.h"
#elif defined(ETYPE_P2_FLOAT)
#include "pfcomp.h"
#elif defined(ETYPE_P2_DOUBLE)
#include "pdcomp.h"
#elif defined(ETYPE_P2_LONG_DOUBLE)
#include "pldcomp.h"
#elif defined(ETYPE_STRING)
#include "strcomp.h"
#elif defined(ETYPE_COLLATED_STRING)
#include "cstr_comp.h"

#else
#error "PLEASE DEFINE SOME TYPE!"
#endif          /* defined(ETYPE_... */

/*
** Prototypes for sorting
*/
#include "genproto.h"



/*
For partitions of zero length, there is nothing to do.
This is the optimal sort for zero items.
*/
PRELUDE
void            INSERTZERO(Etype array[])
{
    return;
}

/*
For partitions of length one, there is nothing to do.
This is the optimal sort for one item.
*/
PRELUDE
void            INSERTONE(Etype array[])
{
    return;
}

/*
For partitions of length two, we either reverse it or leave it alone.
This is the optimal sort for two items.
*/
PRELUDE
void            INSERTTWO(Etype array[])
{
    if (GT(array[0], array[1]))
        SWAP(&array[0], &array[1]);
    return;
}

/*
Optimal treatment for small partitions of length 3.
This is the optimal sort for three items.
*/
PRELUDE
void            INSERTTHREE(Etype array[])
{
    if (LT(array[0], array[1])) {
        if (LT(array[1], array[2]))
            return;
        else if (LT(array[0], array[2]))
            SWAP(&array[1], &array[2]);
        else {
            Etype           Tmp = array[0];
            array[0] = array[2];
            array[2] = array[1];
            array[1] = Tmp;
        }
    } else {
        if (LT(array[0], array[2]))
            SWAP(&array[0], &array[1]);
        else if (LT(array[1], array[2])) {
            Etype           Tmp = array[0];
            array[0] = array[1];
            array[1] = array[2];
            array[2] = Tmp;
        } else
            SWAP(&array[0], &array[2]);
    }
    return;
}

/*
Optimal treatment for small partitions of length 4.
This is the optimal sort for four items.
*/
PRELUDE
void            INSERTFOUR(Etype array[])
{
    Etype           temp;
    if (GT(array[0], array[1])) {
        temp = array[0];
        array[0] = array[1];
        array[1] = temp;
    }
    if (GT(array[2], array[3])) {
        temp = array[2];
        array[2] = array[3];
        array[3] = temp;
    }
    if (GT(array[1], array[2])) {
        if (GT(array[0], array[3])) {
            temp = array[0];
            array[0] = array[2];
            array[2] = temp;
            temp = array[1];
            array[1] = array[3];
            array[3] = temp;
        } else {
            temp = array[1];
            array[1] = array[2];
            array[2] = temp;
            if (GT(array[0], array[1])) {
                temp = array[0];
                array[0] = array[1];
                array[1] = temp;
            }
            if (GT(array[2], array[3])) {
                temp = array[2];
                array[2] = array[3];
                array[3] = temp;
            }
        }
    }
}

/*
In practice, this "optimal" treatment for partitions of length 5
seem to slow the sort down rather than speed it up.
*/
#ifdef MY_CACHE_IS_ENORMOUS
#include "sort5.h"
#endif


/*
** Algorithm M, from:
**  "The Art of Computer Programming, Volume 3: Sorting and Searching",
**  Donald Ervin Knuth, Addison-Wesley, Hardcover, 2nd edition,
**  Published May 1998, ISBN 0201896850
**  Page 111.
**
** This is a straightforward implementation directly from his description.
** While the primary use of Merge Exchange sorting is parallel supercomputer
** sorting of large batches of data, this version is to be tested for use
** on very tiny partitions (specifically 256 items or less)
*/
static const unsigned shiftedbit[] =
{                               /* First two items are just placeholders */
    0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8,
    16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32,
    32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
    32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128,
    128, 128, 128, 128, 128, 128
};

PRELUDE
void            BATCHER(Etype A[], int N)
{
    unsigned        p,
                    q,
                    r,
                    d;
    unsigned        i;

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

    default:

        assert(N <= 256);

/* M1: */
        p = shiftedbit[N];
/* M2: */
        do {
            q = shiftedbit[N];
            r = 0;
            d = p;
    M3:
            for (i = 0; i < N - d; i++) {
                if ((i & p) == r) {
                    Etype           tmp;
                    /* M4: */
                    if (GT(A[i], A[i + d])) {
                        tmp = A[i];
                        A[i] = A[i + d];
                        A[i + d] = tmp;
                    }
                }
            }
/* M5: */
            if (q != p) {
                d = q - p;
                q >>= 1;
                r = p;
                goto M3;        /* Are you going to argue with Knuth? */
            }
/* M6: */
            p >>= 1;
        }
        while (p > 0);
    }
}

/*
Straightforward linear insertion.  Binary insertion is better, and
Shell-sort is better yet.  Don't use this for real sorting work.
*/
PRELUDE
void            LINEARINSERTION(Etype a[], unsigned long n)
{
    unsigned long   i,
                    j;
    Etype           tmp;

    for (i = 1; i < n; i++)     /* look for insertion point. */
        for (j = i; j > 0 && GT(a[j - 1], a[j]); j--) {
            /* Move the others down and insert it. */
            tmp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = tmp;
        }
}

/*
This is a straightforward binary insertion sort.
Binary insertion is much faster on average compared to linear insertion.
Shell-sort is even better, according to my calculations.  You might
want to benchmark both binary insertion and shell-sort, but I suspect
shell-sort will outperform binary insertion on most systems.
*/
PRELUDE
void            INSERTIONSORT(Etype array[], unsigned long count)
{
    unsigned long   partition;  /* The end of a new partition */
    long            beg;        /* Search beginning here (this moves toward
                                 * ipg) */
    long            ipg;        /* Current guess for the insertion point
                                 * (average of beg+end) */
    long            end;        /* Search ending here (this moves toward ipg) */
    Etype           temp;       /* Hold one elemennt of the array in
                                 * temporary storage */
    /* * One element is sorted by definition. * Form larger and larger
     * ordered partitions * until the entire array is correctly ordered */
    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:

/* Seems like a good idea, but it does not really help.
I left this in here so you won't bother with it.  Or if
you do want to try it, you can just remove the comments.