radix sort

Solutions on MaxInterview for radix sort by the best coders in the world

showing results for - "radix sort"
Stefano
05 Mar 2018
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]))
Laura
10 May 2018
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 
Juliana
25 Jun 2017
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}
Giulio
17 Jan 2021
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
queries leading to this page
radix sort implementation c 2b 2b radix sorting algorithmwhat is radix sort 3fbriefly describe how radix sort works when to use radix sortradix sorting algorithmradix sorting machineradix sort auxiliary complexityusing radix sort to sort the following set of numbers 3a 324 2c 281 2c 76 2c 823 2c 441 2c 214 2c 712 2c 234 2c 114 2c 633 after one pass 2c the array would look like 3a 2aradix sortwhat can radix sort sortsorting integers radix sortradix sort code in c 2b 2bradix search complexityradixsort time complexityradix sort stable or notwhen does radix sort result in best caseradix sort 3fradix sort analysiswhat is radix sortwhich sort requires less memory as compared to radix sortradix sort algorithmwhat type of sort is radix sortradix sort pseudocodeis radix sort comparison basedradix sort algorithm in ctime complexity of radix sort worst caseusing the radix sort running time of radix sortradix sort algorithm pseudocoderadix sort radix sort orderradix sort implementradix sort time complexityradix sort exampleradix sort complexityradixsort pseudocodecan any ssort nbe used in radixwhy os does radix sortradix sort tradix sort recurrence relation radix sortradix sort pseudo code radix sortihow radix sort worksradix sort visradix sort is also known ashow to do radix sortradix sort python tutorialwhat is a radix sortlsd radix sortdo you need counting sort for radix sortradix sortersort requires less memoery as compare to radix sortradix sort using averageradix sort space complexityis radix sort a merge sort algorithm 3fthe sort that divides the problem size according to the index of the items is radixw3schools radix 4complexity radix sort algorithm for radix sortc maximum radix sort using arrayradix shortsimple radix sort program in cradix sort space and time complexitytotal iterations for radix sortradix sort order time complexityradix sort asymophticcounting sort used in radix sort is replaced by quick sortrecurrence equation radixsortradix algorithmradix sort definitionnumber of passes required to sort using radix sortradix sort codewhat is a radix sortradix sort explainradix sort program in cradix sort big oradix sort pythoncode for radix srotradix sort runtimeradix sort implementationtime complexity of radix sortradix sort is aexample of radix sortradix searchcomplexity of radix sortsort an array of dates in ascending order using radix sortreddix sort in cppradix sort understandradix sort when radix is n 5e2radix sort array in csolve radix sort time complexity analysisradix sort out place algorithmhow does radix sort workis radix sort stablewrite an algorithm and program code for raddix sortradix and shell sort 27is radix sort usedtheoretical performance of radix sortradix sort comparinghow to implement radix sort javaradix sort in cradix sortingradix sort explanationis it possible to useinsertion sortin intermediate steps ofradix sort 3f justify your answerwith consequencesa 29 explain the algorithm to sort the elements using radix sort using linked allocation trace the algorithm for the following data 231 645 413 198 23 547 874 432 765 678 984 386 radix sort in pythonradix sort explainedpseudocode for implementing radix sortwhat is use of radix sort algorithmexplain radix sort with the help of suitable example radix sort python coderadix sort flow chartdigits in radix sortradix sort