datastructures

Radix Sort in Python

Background

  1. Non comparison integer sorting by grouping numbers based on individual digits or radix (base)
  2. Perform iteratively from least significant digit (LSD) to most significant digit (MSD) or recusively from MSD to LSD.
  3. At each iteration, sorting of target digit is based usually on Counting sort as subroutine.
  4. 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 = [0]*(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]

See also:

Resources:

  1. Getting To The Root Of Sorting With Radix Sort
Advertisements

Counting Sort in Python

Background

  1. Sort a collection of objects according to integer keys. Count the number of objects belonging to a specific key value and output the sequence based on both integer key sequence + number of counts in each key.
  2. Running time linear: O(n+k) where n is the number of objects and k is the number of keys.
  3. Keys should not be significant larger than number of objects

Basic Counting Sort

  • With objects as integer key itself.
  • Limited use. Index key not able to modify for extended cases.
import random, math

def basic_counting_sort(tlist, k):
    """ Counting sort algo. Modified existing list. Only for positive integer.
        Args:
            tlist: target list to sort
            k: max value assume known before hand
        Disadv:
            It only does for positive integer and unable to handle more complex sorting (sort by str, negative integer etc)
            It straight away retrieve all data from count_list using count_list index as its ordering.
            Do not have the additional step to modify count_list to capture the actual index in output.
    """

    # Create a count list and using the index to map to the integer in tlist.
    count_list = [0]*(k)

    # loop through tlist and increment if exists
    for n in tlist:
        count_list[n] = count_list[n] + 1

    # Sort in place, copy back into original list
    i=0
    for n in range(len(count_list)):
        while count_list[n] > 0:
            tlist[i] = n
            i+=1
            count_list[n] -= 1

## Create random list for demo counting sort.
random.seed(0)
tgt_list = [random.randint(0,20) for n in range(10)]
print("Unsorted List")
print(tgt_list)

## Perform the counting sort.
print("\nSorted list using basic counting sort")
basic_counting_sort(tgt_list, max(tgt_list)+1)
print(tgt_list)

Counting sort — improved version

  • Taking “get_sortkey ” function that generate the keys based on objects characteristics.
  • Currently, function just return the object itself to work in same way as above but the function can be modified to work with other form of objects e.g. negative integers, string etc.
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 = [0]*(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

## Create random list for demo counting sort.
random.seed(0)
tgt_list = [random.randint(0,20) for n in range(10)]
print("Unsorted List")
print(tgt_list)

## Perform the counting sort.
print("\nSorted list using basic counting sort")
output = counting_sort(tgt_list, max(tgt_list) +1, get_sortkey) # assumption is known the max value in tgtlist  for this case.
print(output)

Simple illustration: Counting sort use for negative numbers

def get_sortkey2(n):
    """ Define the method to retrieve the key
        Shift the key such that the all keys still positive integers
        even though input may be negative
    """
    return n +5

## Create random list for demo counting sort.
random.seed(1)
tgt_list = [random.randint(-5,20) for n in range(10)]
print("Unsorted List")
print(tgt_list)

## Perform the counting sort.
print("\nSorted list using counting sort")
output = counting_sort(tgt_list, 30, get_sortkey2)
print(output)<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>

Resources:

  1. https://www.geeksforgeeks.org/counting-sort/