C++ Program to Implement Radix Sort

This C++ Program demonstrates the implementation of Radix Sort.

Here is source code of the C++ Program to demonstrate the implementation of Radix Sort. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. /* 

2.  * C++ Program To Implement Radix Sort

3.  */

4. #include <iostream>

5. #include <cstdlib>

6. using namespace std;

7. /* 

8.  * get maximum value in arr[]

9.  */ 

10. int getMax(int arr[], int n)

11. {

12.     int max = arr[0];

13.     for (int i = 1; i < n; i++)

14.         if (arr[i] > max)

15.             max = arr[i];

16.     return max;

17. }

18. /* 

19.  * count sort of arr[]

20.  */  

21. void countSort(int arr[], int n, int exp)

22. {

23.     int output[n];

24.     int i, count[10] = {0};

25.     for (i = 0; i < n; i++)

26.         count[(arr[i] / exp) % 10]++;

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

28.         count[i] += count[i - 1];

29.     for (i = n - 1; i >= 0; i--)

30.     {

31.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];

32.         count[(arr[i] / exp) % 10]--;

33.     }

34.     for (i = 0; i < n; i++)

35.         arr[i] = output[i];

36. }

37. /* 

38.  * sorts arr[] of size n using Radix Sort

39.  */   

40. void radixsort(int arr[], int n)

41. {

42.     int m = getMax(arr, n);

43.     for (int exp = 1; m / exp > 0; exp *= 10)

44.         countSort(arr, n, exp);

45. }

47. /*

48.  * Main

49.  */

50. int main()

51. {

52.     int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

53.     int n = sizeof(arr)/sizeof(arr[0]);

54.     radixsort(arr, n);

55.     for (int i = 0; i < n; i++)

56.         cout << arr[i] << " ";

57.     return 0;

58. }

$ g++ radix_sort.cpp
$ a.out
 
2 24 45 66 75 90 170 802
 
------------------
(program exited with code: 1)
Press return to continue