radix sort
# Python program for implementation of Radix Sort
# A function to do counting sort of arr[] according to
# the digit represented by exp.
def countingSort(arr, exp1):
n = len(arr)
# The output array elements that will have sorted arr
output = [0] * (n)
# initialize count array as 0
count = [0] * (10)
# Store count of occurrences in count[]
for i in range(0, n):
index = (arr[i]/exp1)
count[ (index)%10 ] += 1
# Change count[i] so that count[i] now contains actual
# position of this digit in output array
for i in range(1,10):
count[i] += count[i-1]
# Build the output array
i = n-1
while i>=0:
index = (arr[i]/exp1)
output[ count[ (index)%10 ] - 1] = arr[i]
count[ (index)%10 ] -= 1
i -= 1
# Copying the output array to arr[],
# so that arr now contains sorted numbers
i = 0
for i in range(0,len(arr)):
arr[i] = output[i]
# Method to do Radix Sort
def radixSort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed. exp is 10^i
# where i is current digit number
exp = 1
while max1/exp > 0:
countingSort(arr,exp)
exp *= 10
# Driver code to test above
arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr)
for i in range(len(arr)):
print(arr[i])
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]))
import java.io.*;
import java.util.*;
class Radix {
static 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;
}
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n];
int i;
int count[] = new int[10];
Arrays.fill(count,0);
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
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];
}
static void radixsort(int arr[], int n)
{ // Find the maximum number to know number of digits
int m = getMax(arr, n);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
public static void main (String[] args)
{ int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
radixsort(arr, n);
print(arr, n);
}
}
JavaCopy