## Radix sort Introduction

Radix sort orders the contents position by position. For ease of understanding here we restrict for numbers, but it should work with floats, strings, etc. It is a non-comparitive sort unlike many others which need comparison. The idea is: position by position, either starting from LSB or MSB, group the numbers into buckets. When you move to next position again re-order them for that position, while keeping the order of the previous position re-orders. Once all the positions are done, the whole list should be ordered. See, below example output on how the numbers get re-ordered at each pass of position ordering.- Worst case performance is O(kN), k is count of decimal places and N is the input size. Note that we don't take out k.
- In the below example implementation, for re-order of the numbers for each decimal places, instead of doing lots of swaps, we have taken a simple approach. We do two level counting, first occurrence of numbers for each of the possibilities (0, 1,2 ..9) and then second we use that information to find the appropriate positions for placing all the numbers. A temporary buffer is used to place first and then we copy back to original buffer for next level processing.

## Implementation for Radix sort

#include <iostream> using namespace std; void print(int *input, int n) { for (int i = 0; i < n; i++) cout << input[i] << "\t"; } void radixsort(int *input, int n) { int i; // find the max number in the given list. // to be used in loop termination part. int maxNumber = input[0]; for (i = 1; i < n; i++) { if (input[i] > maxNumber) maxNumber = input[i]; } // run the loop for each of the decimal places int exp = 1; int *tmpBuffer = new int[n]; while (maxNumber / exp > 0) { int decimalBucket[10] = { 0 }; // count the occurences in this decimal digit. for (i = 0; i < n; i++) decimalBucket[input[i] / exp % 10]++; // Prepare the position counters to be used for re-ordering the numbers // for this decimal place. for (i = 1; i < 10; i++) decimalBucket[i] += decimalBucket[i - 1]; // Re order the numbers in the tmpbuffer and later copy back to original buffer. for (i = n - 1; i >= 0; i--) tmpBuffer[--decimalBucket[input[i] / exp % 10]] = input[i]; for (i = 0; i < n; i++) input[i] = tmpBuffer[i]; // Move to next decimal place. exp *= 10; cout << "PASS : "; print(input, n); } } const int INPUT_SIZE = 10; int main() { int input[INPUT_SIZE] = {143, 123, 222, 186, 235, 9, 905, 428, 543, 373}; cout << "Input: "; print(input, INPUT_SIZE); radixsort(input,INPUT_SIZE); cout << " Output: "; print(input, INPUT_SIZE); cout << " "; return 0; }

**Output:-**

Input: 143 123 222 186 235 9 905 428 543 373 PASS : 222 143 123 543 373 235 905 186 428 9 PASS : 905 9 222 123 428 235 143 543 373 186 PASS : 9 123 143 186 222 235 373 428 543 905 Output: 9 123 143 186 222 235 373 428 543 905

## 0 comments:

## Post a Comment