hugesort.txt

巨指针类型数据的快速排序法

//**************************************
//     
//INCLUDE files for :Quicksort using hug
//     e pointers
//**************************************
//     
/* +++Date last modified: 05-Jul-1997 */
/*
** Header file for SNIPPETS sorting functions
*/
#ifndef SNIPSORT__H
#define SNIPSORT__H
#include <stddef.h>
#include "dirport.h"
/*
** Prototypes
*/
#ifdef __STDC__
#define strsort _strsort
#endif
void hugesort(void HUGE *basep, unsigned nel,
unsigned width,
int (*comp)(void HUGE *, void HUGE *)); /* Hugesort.C */
void*sortl(void *list, void *(*getnext)(void *),
void (*setnext)(void *, void *),
int (*compare)(void *, void *)); /* Ll_Qsort.C */
void isort(void *base, size_t nmemb, size_t size,
int (*comp)(const void *, const void *));/* Rg_Isort.C */
void qsort(void *, size_t, size_t,
int (*)(const void *, const void *));/* Rg_Qsort.C */
void swap_chars(char *, char *, size_t); /* Rg_Qsort.C */
void quicksort(int v[], unsigned n); /* Rgiqsort.C */
void ssort (void *base, size_t nel, size_t width,
int (*comp)(const void *, const void *));/* Rg_Ssort.C */
void strsort(char **v, unsigned n);/* Strsort.C */
/*
** File: LL_MSORT.C
*/


    typedef struct list_struct {
    struct list_struct *next;
    char *key;
    /* other stuff */
} list;
list *lsort (list *p);
#endif /* SNIPSORT__H */
 
//**************************************
//     
// Name: Quicksort using huge pointers
// Description:huge qsort() -- public do
//     main by Raymond Gardner 6/92. Tested wit
//     h Borland C++ 3.0 (C mode)
// By: Bob Stout (republished under Open
//     Content License)
//

#include "big_mall.h"
#include "snipsort.h"
static void swap(char HUGE *a, char HUGE *b, unsigned n)


    {
    char tmp;
    do


        {
        tmp = *a; *a++ = *b; *b++ = tmp;
    } while ( --n );
}
void hugesort(void HUGE *basep,
unsignednel,
unsignedwidth,
int (*comp)(void HUGE *, void HUGE *))


    {
    char HUGE *i, HUGE *j;
    unsigned int lnel, rnel;
    char HUGE *base = (char HUGE *)basep;
    while (nel > 1)


        {
        swap(base, base + (long)width * (nel / 2), width);
        for (i = base, j = base + (long)width * nel; ; )


            {
            do
            j -= width;
            while ( (*comp)(j, base) > 0 );
            do
            i += width;
            while ( i < j && (*comp)(i, base) < 0 );
            if (i >= j)
            break;
            swap(i, j, width);
        }
        swap(j, base, width);
        lnel = (unsigned)((long)(j - base) / width);
        rnel = nel - lnel - 1;
        j += width;
        if (lnel < rnel)


            {
            hugesort(base, lnel, width, comp);
            base = j;
            nel = rnel;
        }
        else


            {
            hugesort(j, rnel, width, comp);
            nel = lnel;
        }
    }
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
#include "errors.h"
#define PADSIZE 300


    typedef struct x {
    int key;
    char pad[PADSIZE];
} X;
int cmpv(void HUGE *a, void HUGE *b) /* (note void HUGE *) passed here */


    {
    return ((X HUGE *)a)->key < ((X HUGE *)b)->key ? -1 :
    ((X HUGE *)a)->key > ((X HUGE *)b)->key ? 1 : 0;
}
int main(int argc, char **argv)


    {
    X HUGE *v;
    int n;
    int i, j;
    n = 300;/* default element count */
    if (argc > 1)
    n = atoi(argv[1]);
    printf("test with %d elements\n", n);
    if (NULL == (v = BigMalloc(sizeof(X), n)))
    ErrExit("Insufficient memory"); /* be sure we got memory */
    for (i = 0; i < n; ++i) /* random init */


        {
        v[i].key = rand();
        for (j = 0; j < PADSIZE; ++j)
        v[i].pad[j] = rand();
    }
    for (i = 0; i < n; ++i) /* display before */
    printf(" %d", v[i].key);
    printf("\n");
    hugesort(v, n, sizeof(X), cmpv);/* sort it */
    for ( i = 0; i < n; ++i )/* display after */
    printf(" %d", v[i].key);
    printf("\n");
    BigFree(v);
    return 0;
}
#endif /* TEST */