Related Topics
Data Structure
def counting_sort(arr):
# Find the maximum value in the input data
max_val = max(arr)
# Create a counting array with a length equal to the maximum value + 1
counts = [0] * (max_val + 1)
# Traverse the input data, counting the number of occurrences of each distinct element
for val in arr:
counts[val] += 1
# Modify the counting array so that each entry contains the number of elements less than or equal to the index of that entry
for i in range(1, len(counts)):
counts[i] += counts[i-1]
# Traverse the input data in reverse order, placing each element in its correct position in the output array using the information in the counting array
output = [0] * len(arr)
for val in reversed(arr):
index = counts[val] - 1
output[index] = val
counts[val] -= 1
return output
Radix sort works by sorting the input data first on the least significant digit, then on the next least significant digit, and so on, until the most significant digit has been sorted. Here are the steps for radix sort:
Find the maximum value in the input data.
For each digit position (starting with the least significant), use counting sort to sort the input data based on that digit.
Concatenate the sorted output from each digit position to obtain the fully sorted output.
Here’s an example implementation of radix sort in Python:
def radix_sort(arr):
# Find the maximum value in the input data
max_val = max(arr)
# Sort the input data based on each digit position
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
# Create a counting array with a length of 10 (one for each digit)
counts = [0] * 10
# Traverse the input data, counting the number of occurrences of each digit
for val in arr:
digit = (val // exp) % 10
counts[digit] += 1
# Modify the counting array so that each entry contains the number of elements less than or equal to the index of that entry
for i in range(1, len(counts)):
counts[i] += counts[i-1]
# Traverse the input data in reverse order, placing each element in its correct position in the output array using the information in the counting array
output = [0] * len(arr)
for val in reversed(arr
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.