1 /* quicksort, for linked lists */
6 typedef int T; /* type of item to be sorted */
8 typedef struct listTag { /* typical node to be sorted */
14 #define compLT(a,b) (a < b)
15 #define compGT(a,b) (a > b)
17 listNode *partition(listNode *lb, listNode *rb) {
20 int done; /* record if pointers cross (means we're done!) */
22 /********************************************************
23 * partition list [lb..rb], and return pointer to pivot *
24 ********************************************************/
30 /* scan from both ends, swapping when needed */
31 /* care must be taken not to address outside [lb..rb] with pointers */
34 while (compGT(j->data, pivot)) {
39 while (compLT(i->data, pivot)) {
50 /* examine next element */
58 void quickSort(listNode *lb, listNode *rb) {
61 /************************
62 * sort list [lb..rb] *
63 ************************/
67 m = partition(lb, rb);
69 if (m != lb) quickSort(lb, m); /* sort left side */
70 if (m != rb) quickSort(m->next, rb); /* sort right side */
73 int main(int argc, char *argv[]) {
86 maxnum = atoi(argv[1]);
87 if ((p0 = malloc(maxnum * sizeof(listNode))) == 0) {
88 fprintf (stderr, "insufficient memory (a)\n");
94 for (i = 0; i < maxnum; i++) {
95 p0[i].next = p0 + i + 1;
96 p0[i].prev = p0 + i - 1;
100 quickSort(p0, p0 + maxnum-1);