radix sort using average code example
Example 1: Radix Sort in c++
#include <iostream>
using namespace std;
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
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];
}
void radixsort(int arr[], int n)
{
int m = getMax(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
int n = sizeof(arr) / sizeof(arr[0]);
radixsort(arr, n);
print(arr, n);
return 0;
}
Example 2: radix sort
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10,i)) % 10
}
function digitCount(num) {
if(num === 0 ) return 1
return Math.floor(Math.log10(Math.abs(num))) + 1
}
function mostDigitCount(nums) {
let maxDigit = 0
for(let i = 0;i< nums.length;i++) {
maxDigit = Math.max(maxDigit, digitCount(nums[i]))
}
return maxDigit
}
function Radix(nums){
let maxDigitCount = mostDigitCount(nums)
for(let k=0; k< maxDigitCount; k++) {
let digitbucket = Array.from({length:10} , () => [])
for(let i=0; i< nums.length; i++) {
let digit = getDigit(nums[i], k)
digitbucket[digit].push(nums[i])
}
nums = [].concat(...digitbucket)
}
return nums
}
console.log(Radix([23,123, 23333,444444,55555555]))