qsort3.txt

不使用递归的快速排序法

//**************************************
//     
//INCLUDE files for :Non-Recursive ANSI/
//     ISO quicksort function
//**************************************
//     
/* +++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: Non-Recursive ANSI/ISO quicksor
//     t function
// Description:Sorts an array starting a
//     t base, of length nbr_elements, each ele
//     ment of size width_bytes, ordered via co
//     mpare_function, which is called as (*com
//     pare_function)(ptr_to_element1, ptr_to_e
//     lement2) and returns < 0 if element1 
//     < element2, 0 if element1 = element2,
//     > 0 if element1 > element2. Most r
//     efinements are due to R. Sedgewick. See 
//     "Implementing Quicksort Programs", Comm.
//     ACM, Oct. 1978, and Corrigendum, Comm. A
//     CM, June 1979.
// By: Bob Stout (republished under Open
//     Content License)
//
// Inputs:qsort(base, nbr_elements, widt
//     h_bytes, compare_function); 
void *base; 
size_t nbr_elements, width_bytes;
int (*compare_function)(const void *, const void *);
//

/* +++Date last modified: 05-Jul-1997 */
/******************************************************************/
qsort.c -- Non-Recursive ANSI Quicksort function 
public domain by Raymond Gardner, Englewood CO February 1991 
Usage: 
qsort(base, nbr_elements, width_bytes, compare_function); 
void *base; 
size_t nbr_elements, width_bytes;
int (*compare_function)(const void *, const void *);
Sorts an array starting at base, of length nbr_elements, each 
element of size width_bytes, ordered via compare_function, 
which is called as (*compare_function)(ptr_to_element1,
ptr_to_element2) and returns < 0 if element1 < element2,
0 if element1 = element2, > 0 if element1 > element2. 
Most refinements are due to R. Sedgewick. See "Implementing
Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum,
Comm. ACM, June 1979. 
/******************************************************************/
#include <stddef.h> /* for size_t definition */
#include "snipsort.h"
/* prototypes */
void qsort(void *, size_t, size_t,
int (*)(const void *, const void *));
void swap_chars(char *, char *, size_t);
/*
** Compile with -DSWAP_INTS if your machine can access an int at an
** arbitrary location with reasonable efficiency. (Some machines
** cannot access an int at an odd address at all, so be careful.)
*/
#ifdefSWAP_INTS
void swap_ints(char *, char *, size_t);
#define SWAP(a, b) (swap_func((char *)(a), (char *)(b), width))
#else
#define SWAP(a, b) (swap_chars((char *)(a), (char *)(b), size))
#endif
#define COMP(a, b) ((*comp)((void *)(a), (void *)(b)))
#define T7/* subfiles of T or fewer elements will */
/* be sorted by a simple insertion sort */
/* Note! T must be at least 3 */
void qsort(void *basep, size_t nelems, size_t size,
int (*comp)(const void *, const void *))


    {
    char *stack[40], **sp;/* stack and stack pointer*/
    char *i, *j, *limit; /* scan and limit pointers*/
    size_t thresh;/* size of T elements in bytes*/
    char *base; /* base pointer as char * */
    #ifdefSWAP_INTS
    size_t width;/* width of array element */
    void (*swap_func)(char *, char *, size_t); /* swap func pointer*/
    width = size;/* save size for swap routine */
    swap_func = swap_chars; /* choose swap function*/
    if ( size % sizeof(int) == 0 ) {/* size is multiple of ints */
    width /= sizeof(int);/* set width in ints*/
    swap_func = swap_ints; /* use int swap function*/
}
#endif
base = (char *)basep;/* set up char * base pointer */
thresh = T * size;/* init threshold */
sp = stack; /* init stack pointer */
limit = base + nelems * size;/* pointer past end of array */
for ( ;; ) { /* repeat until break... */
if ( limit - base > thresh ) { /* if more than T elements */
/*swap base with middle */
SWAP((((limit-base)/size)/2)*size+base, base);
i = base + size; /* i scans left to right*/
j = limit - size;/* j scans right to left*/
if ( COMP(i, j) > 0 )/* Sedgewick's */
SWAP(i, j);/*three-element sort*/
if ( COMP(base, j) > 0 ) /*sets things up*/
SWAP(base, j);/*so that*/
if ( COMP(i, base) > 0 ) /* *i <= *base <= *j*/
SWAP(i, base);/* *base is pivot element*/
for ( ;; ) { /* loop until break */
do/* move i right */
i += size; /*until *i >= pivot */
while ( COMP(i, base) < 0 );
do/* move j left */
j -= size; /*until *j <= pivot */
while ( COMP(j, base) > 0 );
if ( i > j ) /* if pointers crossed */
break; /* break loop*/
SWAP(i, j);/* else swap elements, keep scanning*/
}
SWAP(base, j); /* move pivot into correct place */
if ( j - base > limit - i ) { /* if left subfile larger */
sp[0] = base; /* stack left subfile base */
sp[1] = j;/*and limit */
base = i; /* sort the right subfile*/
} else { /* else right subfile larger*/
sp[0] = i;/* stack right subfile base */
sp[1] = limit;/*and limit */
limit = j;/* sort the left subfile*/
}
sp += 2; /* increment stack pointer */
} else { /* else subfile is small, use insertion sort */
for ( j = base, i = j+size; i < limit; j = i, i += size )


for ( ; COMP(j, j+size) > 0; j -= size ) {
SWAP(j, j+size);
if ( j == base )
break;
}
if ( sp != stack ) { /* if any entries on stack */
sp -= 2; /* pop the base and limit*/
base = sp[0];
limit = sp[1];
} else/* else stack empty, done*/
break;
}
}
}
/*
** swap nbytes between a and b
*/
static void swap_chars(char *a, char *b, size_t nbytes)


{
char tmp;


do {
tmp = *a; *a++ = *b; *b++ = tmp;
} while ( --nbytes );
}
#ifdefSWAP_INTS
/*
** swap nints between a and b
*/
static void swap_ints(char *ap, char *bp, size_t nints)


{
int *a = (int *)ap, *b = (int *)bp;
int tmp;


do {
tmp = *a; *a++ = *b; *b++ = tmp;
} while ( --nints );
}
#endif