/* Daiwei Chen An implementation of LSD Radix Sort. */ #include #include #include #include #include using namespace std; // Globals #define ARRAY_SIZE 10 #define MIN_NUM 0 #define MAX_NUM 1000 int getMax(int*); void fillArray(int*); void printArray(int*); // to make radix sort easier, we use counting sort void countingSort(int*, int); void radixSort(int*); int main() { srand(time(NULL)); // yay pointers int* nums = new int[ARRAY_SIZE]; fillArray(nums); std::cout << "The randomly generated array: " << std::endl; printArray(nums); // formatting std::cout << std::endl << "The finished sorted array: " << std::endl; radixSort(nums); printArray(nums); std::cout << std::endl; // Clean-up arrays delete[] nums; return 0; } // gets the largest value in nums[] int getMax(int* nums){ int maxNum = nums[0]; for(int i = 1; i < ARRAY_SIZE; i++) if(nums[i] > maxNum) maxNum = nums[i]; return maxNum; } // prints the array void printArray(int* nums){ for(int i = 0; i < ARRAY_SIZE; i++){ cout << nums[i] << "\t"; } std::cout << std::endl; } // fills the array with rand numbers void fillArray(int* nums){ for(int i = 0; i < ARRAY_SIZE; i++){ nums[i] = rand() % (MAX_NUM - MIN_NUM + 1) + MIN_NUM; } } void countingSort(int* nums, int digit){ int* outray = new int[ARRAY_SIZE]; // output array int hashCount[10] = {0}; // Simple hash table with base 10 // stores the number of times the digit appears in hashCount[] for(int i = 0; i < ARRAY_SIZE; i++) hashCount[(nums[i]/digit)%10]++; // adds up the numbers in hashCount to represent actual position for(int i = 0; i < ARRAY_SIZE-1; i++) hashCount[i+1] += hashCount[i]; // put everything in place in the output array for(int i = ARRAY_SIZE-1; i >= 0; i--) outray[--hashCount[(nums[i]/digit)%10]] = nums[i]; // BY THE POWER OF C++ 11, I HAVE THE POWWAAAAA copy(outray, outray+ARRAY_SIZE, nums); // I didn't even know this existed delete[] outray; // rip } void radixSort(int* nums){ // get dat max yoooooo // I'm so tired int datMax = getMax(nums); // counting sort on every digit! digit is represented with 10^i // datMax/digit will become zero once it is lower than 1 // no float, no worrys man for(int digit = 1; datMax/digit > 0; digit *= 10){ countingSort(nums, digit); //printArray(nums); system("pause"); } }

LSD Radix Sort - Ask anything in the comments!