Radix Sort
Time Complexity
| Best | Average | Worst |
|---|---|---|
| Ω(nk) | Θ(nk) | O(nk) |
Space Complexity
| Worst |
|---|
| O(n+k) |
Overview
Radix Sort is a sorting algorithm that distributes elements into separate buckets based on their radix (or base) and then sorts each bucket separately using another stable algorithm. Let's break down its concepts and steps using the animation input list - [504, 232, 004, 771, 263, 390].
Understanding Radix and Radix Sort:
- Radix: It refers to the number of unique digits that can represent a number in a particular number system. For example, the radix for the decimal system is 10.
- Radix Sort Approach: Radix Sort divides the input elements based on their radix (digit position) and sorts them individually. It delegates the sorting to another stable sorting algorithm, such as Counting Sort or Insertion Sort.
Steps of Radix Sort:
- Determine the maximum number and its number of digits: Find the maximum number in the input and determine the number of digits in it.
- Sort based on each digit position: Sort the elements based on their radix, starting from the least significant digit (LSD) to the most significant digit (MSD).
- Use a stable sorting algorithm for each digit position: Sort the elements within each bucket based on their radix using a stable sorting algorithm.
- Repeat for all digit positions: Repeat the sorting process for each digit position until all digits are sorted.
- Concatenate the sorted buckets: Merge the sorted buckets to obtain the final sorted output.
Example with [504, 232, 004, 771, 263, 390]:
- Setup: Determine the maximum number (771) and the number of digits (3).
- Sort by LSD (Least Significant Digit): Sort by ones, then by tenths, and finally by hundreds.
- Subroutine Algorithm: Use a stable sorting algorithm (e.g., Counting Sort) to sort elements within each bucket.
- Time Complexity: O(n * k) in the best, average, and worst cases, where 'n' is the number of elements and 'k' is the number of digits in the maximum number.
- Space Complexity: O(n + k) for the input elements and created buckets.
In conclusion, Radix Sort is not commonly used for general-purpose sorting but has niche applications, such as distributed systems or when sorting only integers. It's efficient for parallel operations when used with a suitable subroutine algorithm, but it's not typically found in popular developer libraries.
Code
In the first example in Python, you can see 2 different subroutine algorithms - insertion sort and counting sort. You can experiment with both by simply replacing the call to 'insertion_sort' with 'counting_sort'.
Even though the animation resembles insertion sort subroutine, it's good to be aware of the counting sort implementation too since it's considered a more traditional Radix sort implementation. The other examples continue with the insertion sort subroutine.
def insertion_sort(arr, sortingDigit):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# Move elements that are greater than key to one position ahead of their current position
while j >= 0 and (arr[j] // sortingDigit) % 10 > (key // sortingDigit) % 10:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def counting_sort(arr, sortingDigit):
n = len(arr)
output = [0] * n
count = [0] * 10
# How many occurrences of each digit in the input array
for i in range(n):
index = arr[i] // sortingDigit
count[index % 10] += 1
# count[i] - stores the position of the next occurrence of that digit
for i in range(1, 10):
count[i] += count[i - 1]
# Build the output array by placing elements in their sorted order
i = n - 1
while i >= 0:
index = arr[i] // sortingDigit
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# Copy the sorted elements back to the original array
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
# Our algorithm of choice - Insertion Sort. We can use another algorithm, like counting sort, too
digitPlace = 1
while max_num // digitPlace > 0:
insertion_sort(arr, digitPlace)
digitPlace *= 10
return arr
array_to_sort = [504, 232, 4, 771, 263, 390];
sorted_array = radix_sort(array_to_sort)
print("Sorted Array:", sorted_array)
// Insertion Sort with adaptation to take into consideration the 'sorting place digit (ones/units, tenths, hundreds)'
function insertionSort(arr, sortingDigit) {
const n = arr.length;
for (let i = 1; i < n; i++) {
const key = arr[i];
let j = i - 1;
// Move elements that are greater than key to one position ahead of their current position
while (j >= 0 && (arr[j] / sortingDigit) % 10 > (key / sortingDigit) % 10) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Radix Sort Function
function radixSort(arr) {
const max = Math.max(...arr);
// Our algorithm of choice - Insertion Sort. We can use another algorithm, like counting sort too
for (let sortingDigit = 1; Math.floor(max / sortingDigit) > 0; sortingDigit *= 10) {
insertionSort(arr, sortingDigit);
}
return arr;
}
const input = [504, 232, 4, 771, 263, 390];
const sortedArray = radixSort(input);
console.log("Sorted Array:", sortedArray);
public class RadixSort {
// Insertion Sort with adaptation to take into consideration the sorting place digit (ones/units, tenths, hundreds)
private static void insertionSort(int[] arr, int sortingDigit) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements that are greater than key to one position ahead of their current position
while (j >= 0 && (arr[j] / sortingDigit) % 10 > (key / sortingDigit) % 10) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Radix Sort Function
public static void radixSort(int[] arr) {
int max = Integer.MIN_VALUE;
for (int num : arr) {
if (num > max) {
max = num;
}
}
// Our algorithm of choice - Insertion Sort. We can use another algorithm, like counting sort too
for (int sortingDigit = 1; max / sortingDigit > 0; sortingDigit *= 10) {
insertionSort(arr, sortingDigit);
}
}
public static void main(String[] args) {
int[] input = {504, 232, 4, 771, 263, 390};
radixSort(input);
System.out.println();
System.out.print("Sorted Array: ");
for (int num : input) {
System.out.print(num + " ");
}
}
}
#include <stdio.h>
// Insertion Sort with adaptation to take into consideration the 'sorting digit (ones/units, tenths, hundreds)'
void insertionSort(int arr[], int n, int sortingDigit) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Move elements that are greater than key to one position ahead of their current position
while (j >= 0 && (arr[j] / sortingDigit) % 10 > (key / sortingDigit) % 10) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// Radix Sort Function
void radixSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// Our algorithm of choice - Insertion Sort. We can use another algorithm, like counting sort too
for (int sortingDigit = 1; max / sortingDigit > 0; sortingDigit *= 10) {
insertionSort(arr, n, sortingDigit);
}
}
int main() {
int input[] = {504, 232, 4, 771, 263, 390};
int n = sizeof(input) / sizeof(input[0]);
radixSort(input, n);
printf("\nSorted Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", input[i]);
}
return 0;
}
<?php
// Insertion Sort with adaptation to take into consideration the 'sorting digit place (ones/units, tenths, hundreds)'
function insertionSort(&$arr, $digitPlace) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
// Move elements that are greater than key to one position ahead of their current position
while ($j >= 0 && ($arr[$j] / $digitPlace) % 10 > ($key / $digitPlace) % 10) {
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $key;
}
}
function radixSort(&$arr) {
$max = max($arr);
// Our algorithm of choice - Insertion Sort. We can use another algorithm, like counting sort, too
for ($digitPlace = 1; floor($max / $digitPlace) > 0; $digitPlace *= 10) {
insertionSort($arr, $digitPlace);
}
}
$input = [504, 232, 4, 771, 263, 390];
radixSort($input);
print_r($input);
?>