DSA Radix Sort
Radix Sort
The least significant digit (the rightmost one) is sorted first in an array using the Radix Sort method.
------ IMAGE MUKAVI -----
A number system’s radix, also known as base, is the total number of distinct digits. There are ten distinct digits in the standard decimal system, ranging from 0 to 9.
Using the radix, a radix sort places decimal values into ten buckets (or containers) corresponding to the digit under consideration, then returns the buckets or containers to the array before going on to the next digit.
The only integers that the non-comparative Radix Sort algorithm can handle are non-negative numbers.
This is how the Radix Sort algorithm is explained:
How it works:
1.The rightmost digit is the least important digit to start with.
2.Values are sorted according to the digit in focus by first placing them in the appropriate bucket according to the digit in focus, and then rearranging them in the array according to the correct sequence.
3.Proceed to the subsequent digit and repeat the previous step’s sorting until no digits remain.
Stable Sorting
For Radix Sort to produce an accurate result, the elements must be sorted in a stable manner.
An algorithm that maintains the order of elements with the same value both before and after sorting is said to be stable. Assume that we have two items, “K” and “L,” with “K” coming before “L” and both having the value “3”. If element “K” still appears before element “L” after the array has been sorted, the sorting process is deemed stable.
Speaking of stable sorting algorithms for the earlier algorithms we examined separately is illogical, as their stability would not affect the outcome. However, because the items in Radix Sort are sorted one digit at a time, it is crucial that the sorting be done steadily.
Therefore, it is crucial to ensure that Radix Sort sorts the elements on each digit position in a stable manner after sorting the elements on the least significant digit and moving on to the next digit. This is because it is important to preserve the sorting work that has already been done on the previous digit position.
The process of the underlying sorting into buckets is shown in the simulation below. Additionally, you have the option to sort in an unstable manner, which will produce an inaccurate result, in order to have a better knowledge of how stable sorting operates. Simply placing elements into buckets from the end of the array rather than the beginning causes instability in the sorting.
------ IMAGE MUKAVI -----
Manual Run Through
Attempting to perform the sorting by hand will help us better grasp Radix Sort’s operation before putting it into a computer language.
Step 1: To fit values with appropriate radices 0 through 9, we begin with an unsorted array and an empty array.
myArray = [ 33, 45, 40, 25, 17, 24]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 2: We begin the sorting process by concentrating on the least important number.
myArray = [ 33, 45, 40, 25, 17, 24]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 3: Using the digit in focus as a guide, we now shift the elements into the appropriate locations in the radix array. The elements in the radixArray are moved to their proper locations after being taken from the beginning of the myArray.
myArray = [ ]
radixArray = [40], [], [], [33], [24], [45, 25], [], [17], [], [] ]
Step 4: The elements are rearranged into the original array, and the least significant digit is now sorted. The beginning of myArray receives elements from the end of the radixArray.
myArray = [ 40, 33, 24, 45, 25, 17 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 5: The following digit comes into focus. Because we sorted in a stable manner, you’ll notice that values 45 and 25 are still in the same order in relation to one another as they were at the beginning.
myArray = [ 40, 33, 24, 45, 25, 17 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
Step 6: Based on the targeted digit, we shift elements into the radix array.
myArray = [ ]
radixArray = [ [], [17], [24, 25], [33], [40, 45], [], [], [], [], [] ]
Step 7: From the rear of radixArray, we move elements back into the beginning of myArray.
myArray = [ 17, 24, 25, 33, 40, 45 ]
radixArray = [ [], [], [], [], [], [], [], [], [], [] ]
The categorization is complete!
The following steps can be seen animated by running the simulation:
------ IMAGE MUKAVI -----
Manual Run Through: What Happened?
It is evident that values are shifted based on the current radix in focus, from the array to the radix array. Subsequently, the values are repositioned within the array for sorting.
As many times as there are digits in a value, we must move the data from the array we want to sort and back again. For instance, we know we need to sort the array three times, once for each digit, if 437 is the highest number that needs to be sorted.
It is also evident that a two-dimensional radix array is required in order to support several values on a given radix, or index.
In order to ensure that the sorting is stable, we also need to transfer data between the two arrays in a way that maintains the order of values with the same radix in focus.
Radix Sort Implementation
In order to apply the Radix Sort algorithm, we require:
1.An array that needs to be sorted contains nonnegative numbers.
2.a two-dimensional array that stores items with the current radix in focus and has indexes 0 through 9.
3.a loop that inserts values into the two-dimensional radix array at the appropriate location using values from the unsorted array.
4.a loop that returns values from the radix array to the original array.
5.an outer loop with the number of digits in the greatest value multiplied by the number of runs.
The code that is produced looks like this:
Example
myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(myArray)
exp = 1
while maxVal // exp > 0:
while len(myArray) > 0:
val = myArray.pop()
radixIndex = (val // exp) % 10
radixArray[radixIndex].append(val)
for bucket in radixArray:
while len(bucket) > 0:
val = bucket.pop()
myArray.append(val)
exp *= 10
print("Sorted array:", myArray)
On line 7,The maximum value 802 is divided by 1 the first time the while loop executes, by 10 the second time, and by 100 the third time. Floor division (“//”) is used for this purpose. Floor division “//” returns an integer and ignores any numbers that are larger than the decimal point.
On line 11,Based on a value’s radix, or digit in focus, the radixArray determines where to place it. For instance, exp will be 10 the second time the outer while loop executes. 17 will result from dividing 170 by 10. The remainder is returned after the “%10” operation divides by 10. In this instance, 17 is divided by 10 once, leaving 7 behind. As a result, index 7 of the radixArray has value 170.
Radix Sort Using Other Sorting Algorithms
It is possible to use Radix Sort in conjunction with any other sorting algorithm as long as it is reliable. This indicates that any stable sorting algorithm, such counting sort or bubble sort, will function when sorting based on a particular digit.
This is an example of a Radix Sort implementation that sorts on individual digits using Bubble Sort:
Example
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
def radixSortWithBubbleSort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
radixArray = [[],[],[],[],[],[],[],[],[],[]]
for num in arr:
radixIndex = (num // exp) % 10
radixArray[radixIndex].append(num)
for bucket in radixArray:
bubbleSort(bucket)
i = 0
for bucket in radixArray:
for num in bucket:
arr[i] = num
i += 1
exp *= 10
myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixSortWithBubbleSort(myArray)
print("Sorted array:", myArray)
Radix Sort Time Complexity
See this article for a broad description of time complexity.
See this page for a more comprehensive and in-depth description of Radix Sort time complexity.
Radix Sort’s temporal complexity is:
O(n⋅k)
This means that Radix Sort depends both on the values that need to be sorted n, and the number of digits in the highest value k.
A best case scenario for Radix Sort is if there are lots of values to sort, but the values have few digits. For example if there are more than a million values to sort, and the highest value is 999, with just three digits. In such a case the time complexity O(n⋅k) can be simplified to just O(n).
A worst case scenario for Radix Sort would be if there are as many digits in the highest value as there are values to sort. This is perhaps not a common scenario, but the time complexity would be O(n2) in this case.
The most average or common case is perhaps if the number of digits k is something like k(n)=logn. If so, Radix Sort gets time complexity O(n⋅logn). An example of such a case would be if there are 1000000 values to sort, and the values have 6 digits.
View the graphic below to see various possible time complexity for Radix Sort.
Run different simulations of Radix Sort to see how the number of operations falls between the worst case scenario O(n2)(red line) and best case scenario O(n) (green line).
------ IMAGE MUKAVI -----
To make it look okay, the bars that indicate the various numbers are scaled to fit the window. This implies that although values with seven digits appear to be only five times larger than values with two digits, in actuality, values with seven digits are five thousand times larger!
If we are holding n additionally k Thus, the number of operations is the same for the “Random,” “Descending,” and “Ascending” possibilities in the scenario above. This is so because all three scenarios have the same outcome.
