0% completed
Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It sorts numbers starting from the least significant digit (LSD) to the most significant digit (MSD). This method ensures that numbers are sorted correctly at each digit level before moving to the next. Radix Sort uses a stable sorting algorithm, typically Counting Sort, as a subroutine to sort digits.
The key idea is to sort the numbers digit by digit, ensuring that after each pass, the numbers are partially sorted based on the current digit. This process is repeated for each digit position, resulting in a fully sorted array. Radix Sort is particularly effective for sorting large numbers or fixed-length strings, where the number of digits (or characters) is constant.
Step-by-Step Algorithm
-
Find the Maximum Value in the Array
-
Traverse the array to find the maximum value.
- It is used to determine the number of digits in the largest number, which dictates how many times we need to apply Counting Sort.
-
-
Process Each Digit Starting from the Rightmost
- Radix Sort processes each digit position from the least significant to the most significant.
- Start with the Rightmost Digit: Begin by sorting the array based on the rightmost digit (ones place) using Counting Sort. This is done by setting
exp
to1
. - Move Left Digit by Digit: Increase
exp
by multiplying it by 10 to move to the next digit to the left (tens place, hundreds place, etc.). - Repeat for All Digits: Continue this process until you've processed all digits of the largest number. Each time, the array gets sorted more accurately as you move leftward.
-
Counting Sort Based on Digit Position
- Initialize Count Array:
- Create a count array to store the frequency of digits (0-9).
- Initialize the count array to zero.
- Count Digit Occurrences:
- Traverse the input array and count occurrences of each digit at the current digit position.
- Cumulative Count:
- Modify the count array to store cumulative counts.
- This helps in determining the positions of the digits in the output array.
- Build Output Array:
- Traverse the input array in reverse order.
- Place each number in the output array based on the current digit's position indicated by the count array.
- Decrement the count for each digit after placing the number in the output array.
- Copy to Original Array:
- Copy the sorted output array back to the original array for the next iteration.
- Initialize Count Array:
Algorithm Walkthrough
Input: array1 = [180, 55, 85, 90, 903, 243, 2, 6]
-
Find the Maximum Value
- Maximum value = 903
-
Digit Position: Units (exp = 1)
-
Count Digit Occurrences:
- Initialize count array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- Counting digit occurrences:
- For
180
: digit = 0, count array becomes[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- For
55
: digit = 5, count array becomes[1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
- For
85
: digit = 5, count array becomes[1, 0, 0, 0, 0, 2, 0, 0, 0, 0]
- For
90
: digit = 0, count array becomes[2, 0, 0, 0, 0, 2, 0, 0, 0, 0]
- For
903
: digit = 3, count array becomes[2, 0, 0, 1, 0, 2, 0, 0, 0, 0]
- For
243
: digit = 3, count array becomes[2, 0, 0, 2, 0, 2, 0, 0, 0, 0]
- For
2
: digit = 2, count array becomes[2, 0, 1, 2, 0, 2, 0, 0, 0, 0]
- For
6
: digit = 6, count array becomes[2, 0, 1, 2, 0, 2, 1, 0, 0, 0]
- For
- Initialize count array:
-
Cumulative Count:
- Cumulative count array:
[2, 2, 3, 5, 5, 7, 8, 8, 8, 8]
- Cumulative count array:
-
Build Output Array:
- Traverse the input array in reverse order:
- For
6
: digit = 6, place6
at indexcount[6]- 1 = 8 - 1 = 7
.- Decrement count[6] by 1. count array becomes
[2, 2, 3, 5, 5, 7, 7, 8, 8, 8]
. - output array becomes
[0, 0, 0, 0, 0, 0, 0, 6]
.
- Decrement count[6] by 1. count array becomes
- For
2
: digit = 2, place2
at indexcount[2] - 1 = 3 - 1 = 2
.- count array becomes
[2, 2, 2, 5, 5, 7, 7, 8, 8, 8]
. - output array becomes
[0, 0, 2, 0, 0, 0, 0, 6]
.
- count array becomes
- For
243
: digit = 3, place243
at index4
.- count array becomes
[2, 2, 2, 4, 5, 7, 7, 8, 8, 8]
. - output array becomes
[0, 0, 2, 0, 243, 0, 0, 6]
.
- count array becomes
- For
903
: digit = 3, place903
at index3
.- count array becomes
[2, 2, 2, 3, 5, 7, 7, 8, 8, 8]
. - output array becomes
[0, 0, 2, 903, 243, 0, 0, 6]
.
- count array becomes
- For
90
: digit = 0, place90
at index1
.- count array becomes
[1, 2, 2, 3, 5, 7, 7, 8, 8, 8]
. - output array becomes
[0, 90, 2, 903, 243, 0, 0, 6]
.
- count array becomes
- For
85
: digit = 5, place85
at index6
.- count array becomes
[1, 2, 2, 3, 5, 6, 7, 8, 8, 8]
. - output array becomes
[0, 90, 2, 903, 243, 0, 85, 6]
.
- count array becomes
- For
55
: digit = 5, place55
at index5
- count array becomes
[1, 2, 2, 3, 5, 5, 7, 8, 8, 8]
. - output array becomes
[0, 90, 2, 903, 243, 55, 85, 6]
.
- count array becomes
- For
180
: digit = 0, place180
at index0
.- count array becomes
[0, 2, 2, 3, 5, 5, 7, 8, 8, 8]
. - output array becomes
[180, 90, 2, 903, 243, 55, 85, 6]
.
- count array becomes
- For
- Traverse the input array in reverse order:
-
Copy to Original Array:
array
becomes[180, 90, 2, 903, 243, 55, 85, 6]
-
-
Digit Position: Tens (exp = 10)
-
Count Digit Occurrences:
- Initialize count array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- Counting digit occurrences:
- count: [3, 0, 0, 0, 1, 1, 0, 0, 2, 1]`
- Initialize count array:
-
Cumulative Count:
- Cumulative count array:
[3, 3, 3, 3, 4, 5, 5, 5, 7, 8]
- Cumulative count array:
-
Build Output Array:
- Traverse the input array in reverse order:
- For
6
: digit = 0, place6
at index2
.- count array becomes
[2, 3, 3, 3, 4, 5, 5, 5, 7, 8]
. - output array becomes
[0, 0, 6, 0, 0, 0, 0, 0]
- count array becomes
- For
85
: digit = 8, place85
at index6
.- count array becomes
[2, 3, 3, 3, 4, 5, 5, 5, 6, 8]
. - output array becomes
[0, 0, 6, 0, 0, 0, 85, 0]
- count array becomes
- For
55
: digit = 5, place55
at index4
.- count array becomes
[2, 3, 3, 3, 4, 4, 5, 5, 6, 8]
. - output array becomes
[0, 0, 6, 0, 55, 0, 85, 0]
- count array becomes
- For
243
: digit = 4, place243
at index3
.- count array becomes
[2, 3, 3, 3, 3, 4, 5, 5, 6, 8]
. - output array becomes
[0, 0, 6, 243, 55, 0, 85, 0]
- count array becomes
- For
903
: digit = 0, place903
at index1
.- count array becomes
[1, 3, 3, 3, 3, 4, 5, 5, 6, 8]
. - output array becomes
[0, 903, 6, 243, 55, 0, 85, 0]
- count array becomes
- For
2
: digit = 0, place2
at index0
.- count array becomes
[0, 3, 3, 3, 3, 4, 5, 5, 6, 8]
. - output array becomes
[2, 903, 6, 243, 55, 0, 85, 0]
- count array becomes
- For
90
: digit = 9, place90
at index7
.- count array becomes
[0, 3, 3, 3, 3, 4, 5, 5, 6, 7]
. - output array becomes
[2, 903, 6, 243, 55, 0, 85, 90]
- count array becomes
- For
180
: digit = 8, place180
at index5
.- count array becomes
[0, 3, 3, 3, 3, 4, 5, 5, 5, 7]
. - output array becomes
[2, 903, 6, 243, 55, 180, 85, 90]
- count array becomes
- For
- Traverse the input array in reverse order:
-
Copy to Original Array:
array
becomes[2, 903, 6, 243, 55, 180, 85, 90]
-
-
Digit Position: Hundreds (exp = 100)
-
Count Digit Occurrences:
- Initialize count array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- Counting digit occurrences:
- count:
[5, 1, 1, 0, 0, 0, 0, 0, 0, 1]
- count:
- Initialize count array:
-
Cumulative Count:
- Cumulative count array:
[5, 6, 7, 7, 7, 7, 7, 7, 7, 8]
- Cumulative count array:
-
Build Output Array:
- Traverse the input array in reverse order:
- For
90
: digit = 0, place90
at index4
.- count array becomes
[4, 6, 7, 7, 7, 7, 7, 7, 7, 8]
. - output array becomes
[0, 0, 0, 0, 90, 0, 0, 0]
- count array becomes
- For
85
: digit = 0, place85
at index3
.- count array becomes
[3, 6, 7, 7, 7, 7, 7, 7, 7, 8]
. - output array becomes
[0, 0, 0, 85, 90, 0, 0, 0]
- count array becomes
- For
180
: digit = 1, place180
at index5
.- count array becomes
[3, 5, 7, 7, 7, 7, 7, 7, 7, 8]
. - output array becomes
[0, 0, 0, 85, 90, 180, 0, 0]
- count array becomes
- For
55
: digit = 0, place55
at index2
.- count array becomes
[2, 5, 7, 7, 7, 7, 7, 7, 7, 8]
. - output array becomes
[0, 0, 55, 85, 90, 180, 0, 0]
- count array becomes
- For
243
: digit = 2, place243
at index6
.- count array becomes
[2, 5, 6, 7, 7, 7, 7, 7, 7, 8]
. - output array becomes
[0, 0, 55, 85, 90, 180, 243, 0]
- count array becomes
- For
6
: digit = 0, place6
at index1
.- count array becomes
[1, 5, 6, 7, 7, 7, 7, 7, 7, 8]
. - output array becomes
[0, 6, 55, 85, 90, 180, 243, 0]
- count array becomes
- For
903
: digit = 9, place903
at index7
.- count array becomes
[1, 5, 6, 7, 7, 7, 7, 7, 7, 7]
. - output array becomes
[0, 6, 55, 85, 90, 180, 243, 903]
- count array becomes
- For
2
: digit = 0, place2
at index0
.- count array becomes
[0, 5, 6, 7, 7, 7, 7, 7, 7, 7]
. - output array becomes
[2, 6, 55, 85, 90, 180, 243, 903]
- count array becomes
- For
- Traverse the input array in reverse order:
-
Copy to Original Array:
array
becomes[2, 6, 55, 85, 90, 180, 243, 903]
-
Code
Complexity Analysis
Time Complexity
- Finding the maximum value: O(n)
- Counting Sort for each digit:
- Counting occurrences: O(n)
- Building the cumulative count: O(k)
- Placing numbers in the output array: O(n)
- Copying back to the original array: O(n)
- Number of digits (d): log_b(k), where k is the range of input values and b is the base (10 for decimal system).
Overall time complexity: O(d * (n + k)), where d is the number of digits, n is the number of elements, and k is the range of the digits.
Space Complexity
- Count array: O(k)
- Output array: O(n)
Overall space complexity: $O(n + k)%
Real-Time Applications of Radix Sort
- Sorting large integers: Useful for sorting large sets of integers efficiently.
- Fixed-length string sorting: Sorting fixed-length strings, such as sorting by date or IP addresses.
- Telephone numbers: Sorting telephone numbers where the number of digits is fixed.
- Account numbers: Organizing bank account numbers which are typically of fixed length.
- Postcode sorting: Efficiently sorting postcodes or ZIP codes.
- Data processing in databases: Optimizing the sorting of fixed-length keys in databases.
- Digital image processing: Sorting pixel values in image processing applications where each pixel can be treated as a multi-digit number.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible