radix sort

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