Radix Sort Algorithm.

Write a C++ program to implement Radix Sort Algorithm.

Program Code:

#include <iostream>

using namespace std;

int n = 10;

void display(int *input, int m)

{

 for (int i = 0; i < m; i++)

cout << input[i] << "\t";

}

void radix_sort(int *input, int m)

{

int i;

int maxNumber = input[0];

for (i = 1; i < m; i++)

{

if (input[i] > maxNumber)

maxNumber = input[i];

}

int exp = 1;

int *tmpBuffer = new int[m];

while (maxNumber / exp > 0)

{

int decimalBucket[10] = { 0 };

for (i = 0; i < m; i++)

decimalBucket[input[i] / exp % 10]++;

for (i = 1; i < 10; i++)

decimalBucket[i] += decimalBucket[i - 1];

for (i = m - 1; i >= 0; i--)

tmpBuffer[--decimalBucket[input[i] / exp % 10]] = input[i];

for (i = 0; i < m; i++)

input[i] = tmpBuffer[i];

exp *= 10;

cout << "\n PASS   : ";

print(input, n);

} 

int main()

{

int input[n] = {174, 223, 422, 386, 435, 19, 905, 726, 643, 863};

cout << "Input is : ";

print(input, n);

radix_sort(input,n);

cout<<endl;

cout << "Output is : ";

display(input, n);

cout <<endl;

return 0;

}

The program output is tested on www.jdoodle.com

Output:

Input is  : 174    223   422 386 435  19 905 726 643 863

PASS   : 422 223 643 863 174 435 905 386 726 19

PASS   : 905 19 422 223 726 435 643 863 174 386

PASS   : 19 174  223 386 422 435 643 726 863 905

Output is : 19 174 223 386 422 435 643 726 863 905

Thanks

Mukesh Rajput