// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Radix sort implementation #include "book.h" // Include comparator functions #include "compare.h" extern int THRESHOLD; int POW2[9] = {1, 2, 4, 8, 16, 32, 64, 128, 256}; #define pow2(X) POW2[X] template void radix(E A[], E B[], int n, int k, int r, int cnt[]) { // cnt[i] stores number of records in bin[i] int j; for (int i=0, rtoi=1; i=0; j--) B[--cnt[(getKey::key(A[j])/rtoi)%r]] = A[j]; for (j=0; j void sort(E* array, int n) { static E* temp = NULL; static int* cnt = NULL; Assert(THRESHOLD > 0, "Need to set THRESHOLD"); if (temp == NULL) temp = new E[n]; // Declare temp array if (cnt == NULL) cnt = new int[pow2(THRESHOLD)]; // Declare temp array radix(array, temp, n, (sizeof(E) * 8)/THRESHOLD, pow2(THRESHOLD), cnt); } #include "sortmain.cpp" int main(int argc, char** argv) { return sortmain(argc, argv); }