1function getDigit(num, i) {
2 return Math.floor(Math.abs(num) / Math.pow(10,i)) % 10
3}
4
5function digitCount(num) {
6 if(num === 0 ) return 1
7 return Math.floor(Math.log10(Math.abs(num))) + 1
8}
9
10function mostDigitCount(nums) {
11 let maxDigit = 0
12 for(let i = 0;i< nums.length;i++) {
13 maxDigit = Math.max(maxDigit, digitCount(nums[i]))
14 }
15 return maxDigit
16}
17
18function Radix(nums){
19 let maxDigitCount = mostDigitCount(nums)
20 for(let k=0; k< maxDigitCount; k++) {
21 let digitbucket = Array.from({length:10} , () => [])
22 for(let i=0; i< nums.length; i++) {
23 let digit = getDigit(nums[i], k)
24 digitbucket[digit].push(nums[i])
25 }
26 nums = [].concat(...digitbucket)
27 }
28 return nums
29}
30
31console.log(Radix([23,123, 23333,444444,55555555]))
1Radix-Sort(A, d)
2 for j = 1 to d do
3 int count[10] = {0};
4 for i = 0 to n do
5 count[key of(A[i]) in pass j]++
6 for k = 1 to 10 do
7 count[k] = count[k] + count[k-1]
8 for i = n-1 downto 0 do
9 result[ count[key of(A[i])] ] = A[j]
10 count[key of(A[i])]--
11 for i=0 to n do
12 A[i] = result[i]
13 end for(j)
14 end func
1//Code by Soumyadeep
2//insta id: @soumyadepp
3
4#include <bits/stdc++.h>
5#define ll long long
6
7using namespace std;
8
9int maxElement(vector<int> arr)
10{
11 int m = arr[0];
12 for (int i = 0; i < arr.size(); i++)
13 {
14 if (arr[i] > m)
15 m = arr[i];
16 }
17 return m;
18}
19
20int digitCnt(int x)
21{
22 int z = x;
23 int c = 1;
24 while (z)
25 {
26 z /= 10;
27 c++;
28 }
29 return c;
30}
31void radixSort(vector<int> &arr)
32{
33 int x = maxElement(arr); //O(N)
34 int countDigits = digitCnt(x); //O(numberofdigitsinx)
35 for (int i = 1; i <= countDigits; i++) //runs number of digits in maximum element in the array
36 {
37 vector<int> holder[10];
38 for (int j = 0; j < arr.size(); j++) //O(N)
39 {
40 int m = i;
41 int k;
42 int p = arr[j];
43 while (m) //O(logN)
44 {
45 k = p % 10;
46 p /= 10;
47 m--;
48 }
49 holder[k].push_back(arr[j]);
50 }
51 arr.clear();
52 for (int c = 0; c < 10; c++)
53 {
54 arr.insert(arr.end(), holder[c].begin(), holder[c].end());
55 }
56 }
57 //approx O(ND)
58}
59int main()
60{
61 int t;
62 cin >> t;
63 while (t--)
64 {
65 vector<int> arr;
66 int n, x;
67 cin >> n;
68 for (int i = 0; i < n; i++)
69 {
70 cin >> x;
71 arr.push_back(x);
72 }
73 radixSort(arr);
74 cout << "The sorted array is " << endl;
75
76 for (int i = 0; i < arr.size(); i++)
77 cout << arr[i] << " ";
78 cout << endl;
79 }
80 return 0;
81}
1
2import java.io.*;
3import java.util.*;
4class Radix {
5 static int getMax(int arr[], int n){
6 int mx = arr[0];
7 for (int i = 1; i < n; i++)
8 if (arr[i] > mx)
9 mx = arr[i];
10 return mx;
11 }
12 static void countSort(int arr[], int n, int exp)
13 {
14 int output[] = new int[n];
15 int i;
16 int count[] = new int[10];
17 Arrays.fill(count,0);
18 for (i = 0; i < n; i++)
19 count[ (arr[i]/exp)%10 ]++;
20 // Change count[i] so that count[i] now contains
21 // actual position of this digit in output[]
22 for (i = 1; i < 10; i++)
23 count[i] += count[i - 1];
24 // Build the output array
25 for (i = n - 1; i >= 0; i--){
26 output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
27 count[ (arr[i]/exp)%10 ]--;
28 }
29 for (i = 0; i < n; i++)
30 arr[i] = output[i];
31 }
32 static void radixsort(int arr[], int n)
33 { // Find the maximum number to know number of digits
34 int m = getMax(arr, n);
35 for (int exp = 1; m/exp > 0; exp *= 10)
36 countSort(arr, n, exp);
37 }
38 static void print(int arr[], int n)
39 {
40 for (int i=0; i<n; i++)
41 System.out.print(arr[i]+" ");
42 }
43 public static void main (String[] args)
44 { int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
45 int n = arr.length;
46 radixsort(arr, n);
47 print(arr, n);
48 }
49}
50JavaCopy