Radix sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. It works by sorting the numbers by their least significant digit and then by each subsequent significant digit. This process continues until all digits are sorted. Radix sort can be more efficient than comparison-based sorting algorithms, especially for large lists of integers.
Consider an array with the following elements:
[170, 45, 75, 90, 802, 24, 2, 66]
To sort this array using radix sort, follow these steps:
Let's apply these steps to the example array:
Below is the pseudo code for the radix sort algorithm:
function radixSort(array)
maxNumber = getMax(array)
exp = 1
while maxNumber / exp > 0 do
countSort(array, exp)
exp = exp * 10
end while
end function
function countSort(array, exp)
n = length(array)
output = array of size n
count = array of size 10 with zeros
for i = 0 to n - 1 do
index = (array[i] / exp) % 10
count[index] += 1
end for
for i = 1 to 9 do
count[i] += count[i - 1]
end for
for i = n - 1 down to 0 do
index = (array[i] / exp) % 10
output[count[index] - 1] = array[i]
count[index] -= 1
end for
for i = 0 to n - 1 do
array[i] = output[i]
end for
end function
Explanation:
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
# Example usage:
array = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", array)
radix_sort(array)
print("Sorted array:", array) # Output: [2, 24, 45, 66, 75, 90, 170, 802]
This Python program defines functions to perform radix sort on an array. The counting_sort function sorts the array based on the current digit, and the radix_sort function processes each digit starting from the least significant digit.