1 /* ----------------------------------------------------------------------------
3 * ----------------------------------------------------------------------------
4 * Public Domain C Library - http://pdclib.sourceforge.net
5 * This code is Public Domain. Use, modify, and redistribute at will.
6 * --------------------------------------------------------------------------*/
8 void qsort( void * base, size_t nelem, size_t size, int (*cmp) ( const void * e1, const void * e2) ) { /* TODO */ };
10 /* PDPC code - unreviewed
11 /******************************************************************/
12 /* qsort.c -- Non-Recursive ISO C qsort() function */
14 /* Public domain by Raymond Gardner, Englewood CO February 1991 */
15 /* Minor mods by Paul Edwards also public domain */
18 /* qsort(base, nbr_elements, width_bytes, compare_function); */
20 /* size_t nbr_elements, width_bytes; */
21 /* int (*compare_function)(const void *, const void *); */
23 /* Sorts an array starting at base, of length nbr_elements, each */
24 /* element of size width_bytes, ordered via compare_function, */
25 /* which is called as (*compare_function)(ptr_to_element1, */
26 /* ptr_to_element2) and returns < 0 if element1 < element2, */
27 /* 0 if element1 = element2, > 0 if element1 > element2. */
28 /* Most refinements are due to R. Sedgewick. See "Implementing */
29 /* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum, */
30 /* Comm. ACM, June 1979. */
31 /******************************************************************/
34 static void swap_chars(char *, char *, size_t);
37 ** Compile with -DSWAP_INTS if your machine can access an int at an
38 ** arbitrary location with reasonable efficiency. (Some machines
39 ** cannot access an int at an odd address at all, so be careful.)
43 void swap_ints(char *, char *, size_t);
44 #define SWAP(a, b) (swap_func((char *)(a), (char *)(b), width))
46 #define SWAP(a, b) (swap_chars((char *)(a), (char *)(b), size))
49 #define COMP(a, b) ((*comp)((void *)(a), (void *)(b)))
51 #define T 7 /* subfiles of T or fewer elements will */
52 /* be sorted by a simple insertion sort */
53 /* Note! T must be at least 3 */
55 void qsort(void *basep, size_t nelems, size_t size,
56 int (*comp)(const void *, const void *))
58 char *stack[40], **sp; /* stack and stack pointer */
59 char *i, *j, *limit; /* scan and limit pointers */
60 size_t thresh; /* size of T elements in bytes */
61 char *base; /* base pointer as char * */
64 size_t width; /* width of array element */
65 void (*swap_func)(char *, char *, size_t); /* swap func pointer*/
67 width = size; /* save size for swap routine */
68 swap_func = swap_chars; /* choose swap function */
69 if ( size % sizeof(int) == 0 ) { /* size is multiple of ints */
70 width /= sizeof(int); /* set width in ints */
71 swap_func = swap_ints; /* use int swap function */
75 base = (char *)basep; /* set up char * base pointer */
76 thresh = T * size; /* init threshold */
77 sp = stack; /* init stack pointer */
78 limit = base + nelems * size;/* pointer past end of array */
79 for ( ;; ) { /* repeat until break... */
80 if ( limit - base > thresh ) { /* if more than T elements */
81 /* swap base with middle */
82 SWAP(((((size_t)(limit-base))/size)/2)*size+base, base);
83 i = base + size; /* i scans left to right */
84 j = limit - size; /* j scans right to left */
85 if ( COMP(i, j) > 0 ) /* Sedgewick's */
86 SWAP(i, j); /* three-element sort */
87 if ( COMP(base, j) > 0 ) /* sets things up */
88 SWAP(base, j); /* so that */
89 if ( COMP(i, base) > 0 ) /* *i <= *base <= *j */
90 SWAP(i, base); /* *base is pivot element */
91 for ( ;; ) { /* loop until break */
93 i += size; /* until *i >= pivot */
94 while ( COMP(i, base) < 0 );
96 j -= size; /* until *j <= pivot */
97 while ( COMP(j, base) > 0 );
98 if ( i > j ) /* if pointers crossed */
99 break; /* break loop */
100 SWAP(i, j); /* else swap elements, keep scanning*/
102 SWAP(base, j); /* move pivot into correct place */
103 if ( j - base > limit - i ) { /* if left subfile larger */
104 sp[0] = base; /* stack left subfile base */
105 sp[1] = j; /* and limit */
106 base = i; /* sort the right subfile */
107 } else { /* else right subfile larger*/
108 sp[0] = i; /* stack right subfile base */
109 sp[1] = limit; /* and limit */
110 limit = j; /* sort the left subfile */
112 sp += 2; /* increment stack pointer */
113 } else { /* else subfile is small, use insertion sort */
114 for ( j = base, i = j+size; i < limit; j = i, i += size )
115 for ( ; COMP(j, j+size) > 0; j -= size ) {
120 if ( sp != stack ) { /* if any entries on stack */
121 sp -= 2; /* pop the base and limit */
124 } else /* else stack empty, done */
131 ** swap nbytes between a and b
134 static void swap_chars(char *a, char *b, size_t nbytes)
138 tmp = *a; *a++ = *b; *b++ = tmp;
139 } while ( --nbytes );
145 ** swap nints between a and b
148 static void swap_ints(char *ap, char *bp, size_t nints)
150 int *a = (int *)ap, *b = (int *)bp;
153 tmp = *a; *a++ = *b; *b++ = tmp;