This file contains (part of) the code from "Algorithms in C, Third Edition, Parts 1-4," by Robert Sedgewick, and is covered under the copyright and warranty notices in that book. Permission is granted for this code to be used for educational purposes in association with the text, and for other uses not covered by copyright laws, provided that the following notice is included with the code: "This code is from "Algorithms in C, Third Edition," by Robert Sedgewick, Addison Wesley Longman, 1998." Commercial uses of this code require the explicit written permission of the publisher. Send your request for permission, stating clearly what code you would like to use, and in what specific way, to: aw.cse@aw.com CHAPTER 10. Radix Sorting ----- quicksortB(int a[], int l, int r, int w) { int i = l, j = r; if (r <= l || w > bitsword) return; while (j != i) { while (digit(a[i], w) == 0 && (i < j)) i++; while (digit(a[j], w) == 1 && (j > i)) j--; exch(a[i], a[j]); } if (digit(a[r], w) == 0) j++; quicksortB(a, l, j-1, w+1); quicksortB(a, j, r, w+1); } void sort(Item a[], int l, int r) { quicksortB(a, l, r, 0); } ----- #define bin(A) l+count[A] void radixMSD(Item a[], int l, int r, int w) { int i, j, count[R+1]; if (w > bytesword) return; if (r-l <= M) { insertion(a, l, r); return; } for (j = 0; j < R; j++) count[j] = 0; for (i = l; i <= r; i++) count[digit(a[i], w) + 1]++; for (j = 1; j < R; j++) count[j] += count[j-1]; for (i = l; i <= r; i++) aux[l+count[digit(a[i], w)]++] = a[i]; for (i = l; i <= r; i++) a[i] = aux[i]; radixMSD(a, l, bin(0)-1, w+1); for (j = 0; j < R-1; j++) radixMSD(a, bin(j), bin(j+1)-1, w+1); } ----- #define ch(A) digit(A, D) void quicksortX(Item a[], int l, int r, int D) { int i, j, k, p, q; int v; if (r-l <= M) { insertion(a, l, r); return; } v = ch(a[r]); i = l-1; j = r; p = l-1; q = r; while (i < j) { while (ch(a[++i]) < v) ; while (v < ch(a[--j])) if (j == l) break; if (i > j) break; exch(a[i], a[j]); if (ch(a[i])==v) { p++; exch(a[p], a[i]); } if (v==ch(a[j])) { q--; exch(a[j], a[q]); } } if (p == q) { if (v != '\0') quicksortX(a, l, r, D+1); return; } if (ch(a[i]) < v) i++; for (k = l; k <= p; k++, j--) exch(a[k], a[j]); for (k = r; k >= q; k--, i++) exch(a[k], a[i]); quicksortX(a, l, j, D); if ((i == r) && (ch(a[i]) == v)) i++; if (v != '\0') quicksortX(a, j+1, i-1, D+1); quicksortX(a, i, r, D); } ----- void radixLSD(Item a[], int l, int r) { int i, j, w, count[R+1]; for (w = bytesword-1; w >= 0; w--) { for (j = 0; j < R; j++) count[j] = 0; for (i = l; i <= r; i++) count[digit(a[i], w) + 1]++; for (j = 1; j < R; j++) count[j] += count[j-1]; for (i = l; i <= r; i++) aux[count[digit(a[i], w)]++] = a[i]; for (i = l; i <= r; i++) a[i] = aux[i]; } } ----------