function countingSort(arr, size, place){
let output = new Array(size + 1).fill(0);
let max = Math.max(...arr);
let freq = new Array(max + 1).fill(0);
// Calculate count of elements
for (let i = 0; i < size; i++){
const num = Math.floor(arr[i] / place) % 10;
freq[num]++;
}
// Calculate cummulative count
for (let i = 1; i < 10; i++){
freq[i] += freq[i - 1];
}
// Place the elements in sorted order
for (let i = size - 1; i >= 0; i--) {
const num = Math.floor(arr[i] / place) % 10;
output[freq[num] - 1] = arr[i];
freq[num]--;
}
//Copy the output array
for (let i = 0; i < size; i++){
arr[i] = output[i];
}
}
function radixSort(arr, size = arr.length){
//Get the max element
let max = Math.max(...arr);
//Sort the array using counting sort
for(let i = 1; parseInt(max / i) > 0; i *= 10){
countingSort(arr, size, i);
}
}
// Radix sort Java implementation
import java.io.*;
import java.util.*;
class Radix {
// A utility function to get maximum value in arr[]
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;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count, 0);
// Store count of occurrences in count[]
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]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// 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
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
static void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
/*Driver Code*/
public static void main(String[] args)
{
int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
int n = arr.length;
// Function Call
radixsort(arr, n);
print(arr, n);
}
}
/* This code is contributed by Devesh Agrawal */
1 #include <assert.h>
2 #include <limits.h>
3 #include <string.h>
4
5 #include "radixsort.h"
6
7 /* in-place MSB radix sort for null-terminated strings */
8
9 /* helper routine for swapping */
10 static void
11 swapStrings(const char **a, const char **b)
12 {
13 const char *temp;
14
15 temp = *a;
16 *a = *b;
17 *b = temp;
18 }
19
20 /* this is the internal routine that assumes all strings are equal for the
21 * first k characters */
22 static void
23 radixSortInternal(int n, const char **a, int k)
24 {
25 int i;
26 int count[UCHAR_MAX+1]; /* number of strings with given character in position k */
27 int mode; /* most common position-k character */
28 const char **bucket[UCHAR_MAX+1]; /* position of character block in output */
29 const char **top[UCHAR_MAX+1]; /* first unused index in this character block */
30
31 /* loop implements tail recursion on most common character */
32 while(n > 1) {
33
34 /* count occurrences of each character */
35 memset(count, 0, sizeof(int)*(UCHAR_MAX+1));
36
37 for(i = 0; i < n; i++) {
38 count[(unsigned char) a[i][k]]++;
39 }
40
41 /* find the most common nonzero character */
42 /* we will handle this specially */
43 mode = 1;
44 for(i = 2; i < UCHAR_MAX+1; i++) {
45 if(count[i] > count[mode]) {
46 mode = i;
47 }
48 }
49
50 if(count[mode] < n) {
51
52 /* generate bucket and top fields */
53 bucket[0] = top[0] = a;
54 for(i = 1; i < UCHAR_MAX+1; i++) {
55 top[i] = bucket[i] = bucket[i-1] + count[i-1];
56 }
57
58 /* reorder elements by k-th character */
59 /* this is similar to dutch flag algorithm */
60 /* we start at bottom character and swap values out until everything is in place */
61 /* invariant is that for all i, bucket[i] <= j < top[i] implies a[j][k] == i */
62 for(i = 0; i < UCHAR_MAX+1; i++) {
63 while(top[i] < bucket[i] + count[i]) {
64 if((unsigned char) top[i][0][k] == i) {
65 /* leave it in place, advance bucket */
66 top[i]++;
67 } else {
68 /* swap with top of appropriate block */
69 swapStrings(top[i], top[(unsigned char) top[i][0][k]]++);
70 }
71 }
72 }
73
74 /* we have now reordered everything */
75 /* recurse on all but 0 and mode */
76 for(i = 1; i < UCHAR_MAX+1; i++) {
77 if(i != mode) {
78 radixSortInternal(count[i], bucket[i], k+1);
79 }
80 }
81
82 /* tail recurse on mode */
83 n = count[mode];
84 a = bucket[mode];
85 k = k+1;
86
87 } else {
88
89 /* tail recurse on whole pile */
90 k = k+1;
91 }
92 }
93 }
94
95 void
96 radixSort(int n, const char **a)
97 {
98 radixSortInternal(n, a, 0);
99 }
Used to sort integer numbers
sort by:
first sorting the first rightmost digit of every number
then move to the next number to the left and then sort it (if no such digit exists, then it is 0).
after we're totally done, the numbers will be sorted in order.
for example
10, 5, 4, 3, 2
in this case:
if we want to sort these in ascending order
the first sort will result in
10, 2, 3, 4, 5
10 will be the "smallest" number
however, the next sort with the next digit will put things in proper order
In that case we are sorting
1-0, 0-2, 0-3, 0-4, 0-5
1 is (obviously) the largest of the digits.
So it is in the rightest.
The correct order is now 2,3,4,5,10