Hello! Today, we will learn about the Radix Sort algorithm in Python. Radix Sort is one of the sorting algorithms with very favorable space and time complexity, and it is particularly useful for sorting data types such as integers or strings. In this lecture, we will explain the principle of Radix Sort, its implementation method, and how to use Radix Sort through practical problems in detail.
What is Radix Sort?
Radix Sort is a method of sorting that considers each digit of a given number (tens, hundreds, etc.). Radix Sort proceeds in the following steps:
- Start from the lowest digit and distribute based on each digit.
- Gather the distributed numbers to create a sorted list.
- Move to the next digit and repeat the process.
Radix Sort is generally implemented in two ways: LSD (Least Significant Digit) and MSD (Most Significant Digit). This lecture will focus on the LSD method, which starts from the smallest digit.
Time Complexity of Radix Sort
The time complexity of Radix Sort is O(nk), where n is the number of numbers to be sorted and k is the number of digits in the largest number. Radix Sort is classified as a stable sort, which means that the relative order of elements with the same value does not change.
Problem: Sorting Using Radix Sort
Now, let’s solve a problem that applies Radix Sort to sort given integers. The problem is as follows:
Problem Description
When given an array of integers, write a program to sort this array in ascending order using Radix Sort.
Input
- Array of integers:
[170, 45, 75, 90, 802, 24, 2, 66]
Output
Print the array sorted in ascending order.
Problem Solving Process
Now, let’s implement Radix Sort to solve the above problem. First, we will write a helper function called counting_sort that sorts based on each digit as follows. This function sorts the array based on the given digit.
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n # List to store the sorted array
count = [0] * 10 # List to count numbers from 0 to 9
# Count the occurrences of each number based on the current digit
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
# Find the position of each number using cumulative sum
for i in range(1, 10):
count[i] += count[i - 1]
# Create the sorted array
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
# Reflect the sorted result in the original array
for i in range(n):
arr[i] = output[i]
In the above code, the counting_sort function checks the current digit of each number in the input array, counts how many of each number correspond to that digit, and generates sorted results through cumulative sums. Now let’s write the main function to implement Radix Sort.
def radix_sort(arr):
# Find the largest number in the array to determine the number of digits
max_num = max(arr)
# Start sorting from the smallest digit
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
Now, let’s look at the complete implementation of Radix Sort.
def radix_sort(arr):
max_num = max(arr) # Find the maximum value
exp = 1 # Initialize the exponent of the digit
while max_num // exp > 0: # Repeat for the number of digits in the maximum value
counting_sort(arr, exp) # Call counting_sort for the current digit
exp *= 10 # Move to the next digit
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n # List to store the sorted array
count = [0] * 10 # List to count numbers from 0 to 9
# Count the occurrences of each number based on the current digit
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
# Find the position of each number using cumulative sum
for i in range(1, 10):
count[i] += count[i - 1]
# Create the sorted array
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
# Reflect the sorted result in the original array
for i in range(n):
arr[i] = output[i]
# Test code
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Array before sorting:", arr)
radix_sort(arr)
print("Array after sorting:", arr)
Test Results
When the above code is executed, the following results appear:
Array before sorting: [170, 45, 75, 90, 802, 24, 2, 66]
Array after sorting: [2, 24, 45, 66, 75, 90, 170, 802]
By comparing the array before and after sorting, we can see that Radix Sort works well.
Advantages and Disadvantages of Radix Sort
Advantages
- It performs very quickly for specific types of data (integers, strings, etc.).
- Being a stable sort, the order of elements with the same value is preserved.
- It enables efficient sorting when interested in specific digits.
Disadvantages
- It consumes additional memory and requires an array of the same size as the original array.
- It is not suitable for data types other than integers or strings.
- If the range of data is very large, the time complexity may increase.
Conclusion
In this lecture, we learned in detail about Radix Sort and solved a problem of sorting an array through it. Radix Sort is a very useful sorting algorithm in specific situations, so it may frequently appear in algorithm exams. Therefore, it is important to clearly understand the principles of Radix Sort and its actual implementation. In the next session, we will learn about another useful sorting algorithm or data structure. Thank you for reading!