- Non comparison integer sorting by grouping numbers based on individual digits or radix (base)
- Perform iteratively from least significant digit (LSD) to most significant digit (MSD) or recusively from MSD to LSD.
- At each iteration, sorting of target digit is based usually on Counting sort as subroutine.
- Complexity: O(d*n+b)) where b is the base for representing numbers eg 10. d is the number of digits. Close to Linear time if d is constant amount
Counting Sort as subroutine
- Recap on the counting sort. See Counting Sort in Python for more info
- Taking “get_sortkey ” function that generate the keys based on objects characteristics.
- Modified the get_sortkey function to perform radix sort.
import random, math def get_sortkey(n): """ Define the method to retrieve the key """ return n def counting_sort(tlist, k, get_sortkey): """ Counting sort algo with sort in place. Args: tlist: target list to sort k: max value assume known before hand get_sortkey: function to retrieve the key that is apply to elements of tlist to be used in the count list index. map info to index of the count list. Adv: The count (after cum sum) will hold the actual position of the element in sorted order Using the above, """ # Create a count list and using the index to map to the integer in tlist. count_list = *(k) # iterate the tgt_list to put into count list for n in tlist: count_list[get_sortkey(n)] = count_list[get_sortkey(n)] + 1 # Modify count list such that each index of count list is the combined sum of the previous counts # each index indicate the actual position (or sequence) in the output sequence. for i in range(k): if i ==0: count_list[i] = count_list[i] else: count_list[i] += count_list[i-1] output = [None]*len(tlist) for i in range(len(tlist)-1, -1, -1): sortkey = get_sortkey(tlist[i]) output[count_list[sortkey]-1] = tlist[i] count_list[sortkey] -=1 return output
Radix sort with up to 3-digits numbers
- Replace the get_sortkey with the get_sortkey2 which extract the integer based on the digit place and uses the counting sort at each iteration
# radix sort from functools import partial def get_sortkey2(n, digit_place=2): """ Define the method to retrieve the key return the key based on the digit place. Current set base to 10 """ return (n//10**digit_place)%10 ## Create random list for demo counting sort. random.seed(1) tgt_list = [random.randint(20,400) for n in range(10)] print("Unsorted List") print(tgt_list) ## Perform the counting sort. print("\nSorted list using counting sort") output = tgt_list for n in range(3): output = counting_sort(output, 30, partial(get_sortkey2, digit_place=n)) print(output) ## output # Unsorted List # [88, 311, 52, 150, 80, 273, 250, 261, 353, 214] # Sorted list using counting sort # [150, 80, 250, 311, 261, 52, 273, 353, 214, 88] # [311, 214, 150, 250, 52, 353, 261, 273, 80, 88] # [52, 80, 88, 150, 214, 250, 261, 273, 311, 353]