Simtel MSDOS - Coast to Coast/simteldosarchivecoasttocoast2.iso/c/qsort.c

C/C++ Source or Header | 1994-03-04 | 5KB | 180 lines

#define DEBUG
/*    qsort - general purpose quicksort

    Author...
        Copyright (c) 1984  Allen I. Holub

        All rights reserved.
        This program may be copied for personal, non-profit use only.

        Published in Dr. Dobb's Journal #102 (Apr 85).

    Usage...

        Including a #define for DEBUG will make this file a stand-alone
        program which sorts argv and prints the result, along with all
        intermediate stages.  This is pretty instructive if you want to
        see how the quick sort works.

*/

#ifdef DEBUG

static int    Lev=0;        /* recursion level */
static int    Maxlev=0;    /* maximum recursion level */
int Comparisons=0, Exchanges=0;
#endif

typedef int (*PFI)();    /* pointer to a function returning int */
static PFI Comp;        /* pointer to comparison routine */
static int Width;        /* width of an object in bytes */

/*---------------------------------------------------------------------------*/
int argvcmp(s1p,s2p) char **s1p,**s2p;
{
    /*    Comparison routine for sorting an argv like list of pointers
        to strings.  Just remove one level of indirection and call
        strcmp to do the comparison                                        */

#ifdef DEBUG
    register int rval;
    rval=strcmp(*s1p,*s2p);
    printf("level %d: argvcmp(<%s><%s>) = %d\n",Lev,*s1p,*s2p,rval);
    Comparisons++;
    return (rval);
#else
    return (strcmp(*s1p,*s2p));
#endif
}

qsort(base,nel,width,compare)
char *base;
int    nel,width;
int    (*compare)();
{
    /*    Perform a quick sort on an array starting at base.  The
        array is nel elements large and width is the size of a single
        element in bytes.  Compare is a pointer to a comparison routine
        which will be passed pointers to two elements of the array.  It
        should return a negative number if the left-most argument is
        less than the rightmost, 0 if the two arguments are equal, a
        positive number if the left argument is greater than the right.
        (That is, it acts like a "subtract" operator.) If compare is 0
        then the default comparison routine, argvcmp (which sorts an
        argv-like array of pointers to strings), is used.
    */

#ifdef DEBUG
    printf("Sorting %d element array of %d byte elements at 0x%x\n",
        nel,width,base);
    printf("Comparison routine at 0x%x. Unsorted list:\n",compare);
    ptext(nel,base);
#endif
    Width=width;
    Comp=(compare==(PFI)0) ? &argvcmp : compare ;
    if(nel>1)
        rqsort(base,base+((nel-1)*width));
#ifdef DEBUG
    printf("\nSort complete, list is:\n");
    ptext(nel,base);
    printf("Maximum recursion level = %d\n",Maxlev);
    printf("%d comparisons and %d exchanges were performed \n",
    Comparisons, Exchanges);
#endif
}

/*---------------------------------------------------------------------------*/
static rqsort(low,high)
register char *low,*high;
{
    /*    Workhorse function called by the access routine, qsort().
        Not externally accessible.                                        */

    char *pivot,*base;
    static char *a,*b;    /*    Used for exchanges, will not need to retain    */
    static int tmp,i;    /*    their values during the recursion so they    */
                        /*    can be static                                */

#ifdef DEBUG
    printf("New pass, recursion level %d\n",Lev);
    if (Lev>Maxlev) Maxlev=Lev;
#endif
    base=low;        /* remember base address of array    */
    pivot=high;        /* partition off the pivot            */
    high -= Width;

    do
        {while( low<high && (*Comp)(low,pivot) <= 0)  low += Width;
        while( low<high && (*Comp)(high,pivot) >= 0 ) high -= Width;
        if( low < high )    /* exchange low & high */
            {
#ifdef DEBUG
            printf("lev %d: exchanging high: <%s> & low: <%s>\n",
                Lev,*((char **)high), *((char **)low));
#endif
            for ( b=low,a=high,i=Width ; --i>=0 ; )
                {tmp = *b;    /* Exchange *low and *high */
                *b++ = *a;
                *a++ = tmp;
#ifdef DEBUG
    Exchanges++;
#endif
                }
            }
        } while ( low<high );
#ifdef DEBUG
        printf("level %d: Exchanging pivot:<%s>  & low:<%s>\n",
            Lev, *((char **)pivot), *((char**)low) );
#endif
        if( low < pivot && (*Comp)(low, pivot) > 0 )
            for ( b=low,a=pivot,i=Width ; --i >=0 ; )
                {tmp=*b ;    /* Exchange *low and *pivot */
                *b++=*a;
                *a++=tmp;
#ifdef DEBUG
    Exchanges++;
#endif
                }
#ifdef DEBUG
        printf("\nDone with pass, partially sorted list =\n");
        ptext( ((pivot - base)/Width) + 1,base );
        printf("\n");
        ++Lev;
#endif
        low += Width;
        if( high-base < pivot-low )
            {if( low < pivot ) rqsort( low , pivot );
            if(base < high ) rqsort( base , high );
            }
        else
            {if( base < high ) rqsort( base , high );
            if( low < pivot ) rqsort( low , pivot );
            }
#ifdef DEBUG
        --Lev;
#endif
}

/*---------------------------------------------------------------------------*/
/*        Test routine for qsort, compiled if DEBUG is #defined                */

#ifdef DEBUG
static ptext( argc, argv)
int argc;
char **argv;
{
    /*    Print out argv, one element per line    */

    register int i;
    for ( i=1 ; --argc>=0 ; i++ ) printf("%2d: %s\n",i,*argv++);
}

main(argc,argv) int argc; char **argv;
{
    /*    Test routine for qsort.  Sorts argv (less the first element).    */

    qsort(++argv,--argc,sizeof(PFI),0);
}

#endif