You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
65 lines
1.3 KiB
C++
65 lines
1.3 KiB
C++
/*
|
|
* C++ Program To Implement Radix Sort
|
|
*/
|
|
#include <iostream>
|
|
#include <cstdlib>
|
|
using namespace std;
|
|
/*
|
|
* get maximum value in arr[]
|
|
*/
|
|
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)
|
|
{
|
|
int output[n];
|
|
int i, count[10] = {0};
|
|
for (i = 0; i < n; i++)
|
|
count[(arr[i] / exp) % 10]++;
|
|
for (i = 1; i < 10; i++)
|
|
count[i] += count[i - 1];
|
|
for (i = n - 1; i >= 0; i--)
|
|
{
|
|
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
|
|
count[(arr[i] / exp) % 10]--;
|
|
}
|
|
for (i = 0; i < n; i++)
|
|
arr[i] = output[i];
|
|
}
|
|
/*
|
|
* sorts arr[] of size n using Radix Sort
|
|
*/
|
|
void radixsort(int arr[], int n)
|
|
{
|
|
int m = getMax(arr, n);
|
|
for (int exp = 1; m / exp > 0; exp *= 10)
|
|
countSort(arr, n, exp);
|
|
}
|
|
|
|
/*
|
|
* Main
|
|
*/
|
|
int main()
|
|
{
|
|
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
|
|
int n = sizeof(arr)/sizeof(arr[0]);
|
|
radixsort(arr, n);
|
|
for (int i = 0; i < n; i++)
|
|
cout << arr[i] << " ";
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
2 24 45 66 75 90 170 802
|
|
|
|
------------------
|
|
(program exited with code: 1)
|
|
Press return to continue
|