C++ Program to Implement Radix Sort
This is a C++ Program to Sort the Given Data using Radix sort.
- In this algorithm sorting of data is done from least significant digit to most significant digit.
- Here we need 10 different spaces labeled 0 to 9.
- Assume we have ‘n’ number of inputs.
- Let ‘d’ be the maximum number of digit the input data has.
- The time complexity for radix sort is O(n*d).
- Radix sort solves the problem of card sorting by sorting on the least significant digit first.
- Get the maximum value from the input array which has ‘d’ digits.
- Starting from least significant digit, sort the data.
- Take this data as input for next significant digit.
- Run the iteration till d digit.
- Display the result.
- Exit.
Cpp Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include <iostream> using namespace std; // Get maximum value from array. int getMax(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i]; return max; } // Count sort of arr[]. void countSort(int arr[], int n, int exp) { // Count[i] array will be counting the number of array values having that 'i' digit at their (exp)th place. int output[n], i, count[10] = {0}; // Count the number of times each digit occurred at (exp)th place in every input. for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Calculating their cumulative count. for (i = 1; i < 10; i++) count[i] += count[i-1]; // Inserting values according to the digit '(arr[i] / exp) % 10' fetched into count[(arr[i] / exp) % 10]. for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Assigning the result to the arr pointer of main(). for (i = 0; i < n; i++) arr[i] = output[i]; } // Sort arr[] of size n using Radix Sort. void radixsort(int arr[], int n) { int exp, m; m = getMax(arr, n); // Calling countSort() for digit at (exp)th place in every input. for (exp = 1; m/exp > 0; exp *= 10) countSort(arr, n, exp); } int main() { int n, i; cout<<"\nEnter the number of data element to be sorted: "; cin>>n; int arr[n]; for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>arr[i]; } radixsort(arr, n); // Printing the sorted data. cout<<"\nSorted Data "; for (i = 0; i < n; i++) cout<<"->"<<arr[i]; return 0; } |
Output:
1 2 3 4 5 6 7 8 9 10 | Enter the number of data element to be sorted: 5 Enter element 1: 12 Enter element 2: 25 Enter element 3: 42 Enter element 4: 10 Enter element 5: 5 Sorted Data ->5->10->12->25->42 |
