Radix Sort
Radix sort is a non-comparison sorting algorithm. Instead of comparing elements directly, it sorts numbers digit by digit (or character by character), starting from either the least significant digit (LSD).
Example
[170, 45, 75, 90, 802, 24, 2, 66]
Sort First LSD: [170, 90, 802, 2, 24, 45, 75, 66]
Sort Second LSD: [802, 2, 24, 45, 66, 170, 75, 90]
Sort Third LSD: [2, 24, 45, 66, 75, 90, 170, 802]
Time Complexity
O(d * (n + k))
where k: range, d = digits
Effectively o(n) for integers.
Space Complexity
O(n + k)
When to use Radix Sort
- Large number of integers.
- Fix digit length.
- Non-negative numbers.
When Not to use Radix Sort
- Floating point values.
- Very large digits.
- When memory is extremely tight.
function countingSortStable(arr, e) {
let count = new Array(10).fill(0);
for(let x of arr){
let digit = Math.floor(x / e) % 10;
count[digit]++;
}
for(let i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
let sortedArr = new Array(arr.length);
for(let i = arr.length - 1; i >= 0; i--) {
let curr = Math.floor(arr[i] / e) % 10;
let x = count[curr];
sortedArr[x-1] = arr[i];
count[curr]--
}
// modify the original array
for(let i = 0; i < arr.length; i++) {
arr[i] = sortedArr[i];
}
}
function radixSort(arr){
let max = Math.max(...arr);
for(let e = 1; Math.floor(max / e) > 0; e = e * 10){
countingSortStable(arr, e);
}
return arr;
}
let nums = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(nums));
def countingSortStable(arr, e):
count = [0] * 10
for x in arr:
digit = (x // e) % 10
count[digit] += 1
for i in range(1, len(count)):
count[i] = count[i] + count[i - 1]
sortedArr = [0] * len(arr)
for i in range(len(arr) - 1, -1, -1):
curr = (arr[i] // e) % 10
x = count[curr]
sortedArr[x - 1] = arr[i]
count[curr] -= 1
for i in range(len(arr)):
arr[i] = sortedArr[i]
def radixSort(arr):
max_val = max(arr)
e = 1
while max_val // e > 0:
countingSortStable(arr, e)
e *= 10
return arr
nums = [170, 45, 75, 90, 802, 24, 2, 66]
print(radixSort(nums))
import java.util.*;
public class RadixSort {
static void countingSortStable(int[] arr, int e) {
int[] count = new int[10];
for (int x : arr) {
int digit = (x / e) % 10;
count[digit]++;
}
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
int[] sortedArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int curr = (arr[i] / e) % 10;
int x = count[curr];
sortedArr[x - 1] = arr[i];
count[curr]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = sortedArr[i];
}
}
static int[] radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int e = 1; max / e > 0; e = e * 10) {
countingSortStable(arr, e);
}
return arr;
}
public static void main(String[] args) {
int[] nums = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println(Arrays.toString(radixSort(nums)));
}
}
#include <bits/stdc++.h>
using namespace std;
void countingSortStable(vector& arr, int e) {
vector count(10, 0);
for (int x : arr) {
int digit = (x / e) % 10;
count[digit]++;
}
for (int i = 1; i < count.size(); i++) {
count[i] = count[i] + count[i - 1];
}
vector sortedArr(arr.size());
for (int i = arr.size() - 1; i >= 0; i--) {
int curr = (arr[i] / e) % 10;
int x = count[curr];
sortedArr[x - 1] = arr[i];
count[curr]--;
}
for (int i = 0; i < arr.size(); i++) {
arr[i] = sortedArr[i];
}
}
vector radixSort(vector& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
for (int e = 1; maxVal / e > 0; e = e * 10) {
countingSortStable(arr, e);
}
return arr;
}
int main() {
vector nums = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(nums);
for (int x : nums) cout << x << " ";
return 0;
}
#include <stdio.h>
void countingSortStable(int arr[], int n, int e) {
int count[10] = {0};
int sortedArr[n];
for (int i = 0; i < n; i++) {
int digit = (arr[i] / e) % 10;
count[digit]++;
}
for (int i = 1; i < 10; i++) {
count[i] = count[i] + count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int curr = (arr[i] / e) % 10;
int x = count[curr];
sortedArr[x - 1] = arr[i];
count[curr]--;
}
for (int i = 0; i < n; i++) {
arr[i] = sortedArr[i];
}
}
void radixSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
for (int e = 1; max / e > 0; e = e * 10) {
countingSortStable(arr, n, e);
}
}
int main() {
int nums[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(nums) / sizeof(nums[0]);
radixSort(nums, n);
for (int i = 0; i < n; i++)
printf("%d ", nums[i]);
return 0;
}
using System;
using System.Linq;
class Program {
static void countingSortStable(int[] arr, int e) {
int[] count = new int[10];
foreach (int x in arr) {
int digit = (x / e) % 10;
count[digit]++;
}
for (int i = 1; i < count.Length; i++) {
count[i] = count[i] + count[i - 1];
}
int[] sortedArr = new int[arr.Length];
for (int i = arr.Length - 1; i >= 0; i--) {
int curr = (arr[i] / e) % 10;
int x = count[curr];
sortedArr[x - 1] = arr[i];
count[curr]--;
}
for (int i = 0; i < arr.Length; i++) {
arr[i] = sortedArr[i];
}
}
static int[] radixSort(int[] arr) {
int max = arr.Max();
for (int e = 1; max / e > 0; e = e * 10) {
countingSortStable(arr, e);
}
return arr;
}
static void Main() {
int[] nums = {170, 45, 75, 90, 802, 24, 2, 66};
Console.WriteLine(string.Join(" ", radixSort(nums)));
}
}
