Step by Step solution about How to resolve the algorithm Sorting algorithms/Radix sort step by step in the Python programming language

The provided source code contains a collection of functions used to implement the radix sort algorithm. Here's a detailed explanation of each function:

1. getDigit(num, base, digit_num): This function extracts a specific digit from a number. It takes three arguments:

   • num: The input number from which the digit is to be extracted.
   • base: The base of the number system (e.g., 10 for decimal, 2 for binary).
   • digit_num: The position of the digit to be extracted, starting from the least significant digit (position 0).

   The function calculates the digit by performing integer division by base raised to the power of digit_num and then taking the remainder of the division by base. This gives the value of the selected digit.

2. makeBlanks(size): This function creates a list of empty lists to serve as buckets for splitting numbers based on their digits. It takes one argument:

   • size: The number of buckets to create.

   The function returns a list of size empty lists, each of which will be used to hold numbers with a specific digit value.

3. split(a_list, base, digit_num): This function performs radix sorting by splitting a list of numbers into buckets based on the value of a specified digit. It takes three arguments:

   • a_list: The input list of numbers to be sorted.
   • base: The base of the number system being used.
   • digit_num: The position of the digit to consider for splitting.

   The function iterates over the input list, extracts the selected digit from each number using the getDigit function, and appends the number to the appropriate bucket based on the digit value.

4. merge(a_list): This function concatenates the elements of a list of lists into a single list. It takes one argument:

   • a_list: The list of lists to be merged.

   The function iterates over the sublists in the input list and adds all elements to a new list, effectively merging the sublists into one.

5. maxAbs(a_list): This function calculates the maximum absolute value of elements in a list. It takes one argument:

   • a_list: The input list of numbers.

   The function uses a generator expression to calculate the absolute value of each element in the list and then finds the maximum value.

6. split_by_sign(a_list): This function splits a list of numbers into two buckets based on their sign (positive or negative). It takes one argument:

   • a_list: The input list of numbers.

   The function iterates over the input list, and if a number is negative, it is added to the first bucket; otherwise, it is added to the second bucket.

7. radixSort(a_list, base): This function implements the radix sort algorithm on a list of numbers. It takes two arguments:

   • a_list: The input list of numbers to be sorted.
   • base: The base of the number system being used.

   The function first calculates the number of passes required, which is equal to the integer part of the logarithm of the maximum absolute value of the numbers in the list plus 1. Then, it iterates through each pass, calling the split function to divide the list into buckets based on the value of each digit, starting from the least significant digit and moving towards the most significant digit. Finally, it calls the merge function to concatenate the buckets back into a single sorted list.

Alternative Implementations using Generators and Lambdas:

In addition to the functions described above, the source code also includes two alternative implementations of the radix sort algorithm using generators and lambda functions:

1. radix(some_list, idex=None, size=None): This function is a recursive implementation of radix sort that uses generators and lambda functions. It takes three optional arguments:

   • some_list: The input list of numbers to be sorted.
   • idex: The position of the digit to consider for splitting (used internally during recursion).
   • size: The number of digits in the largest number in the list (used internally during recursion).

   The function first initializes idex and size if they are not provided. Then, it uses a generator expression to create a list of bins based on the input size. It iterates over the input list and places each number in its appropriate bin based on the value of the selected digit. Finally, it recursively calls itself to sort each bin and then combines the sorted bins into a single sorted list.

2. flatten(l): This function is a utility function used to flatten a list of lists into a single list. It takes one argument:

   • l: The input list of lists to be flattened.

   The function uses a generator expression to iterate over the sublists and combine their elements into a single list.

3. radix(l, p=None, s=None): This is another recursive implementation of radix sort that uses generators and lambda functions. It takes three optional arguments:

   • l: The input list of numbers to be sorted.
   • p: The position of the digit to consider for splitting (used internally during recursion).
   • s: The number of digits in the largest number in the list (used internally during recursion).

   The function first initializes p and s if they are not provided. It then creates a list of bins based on the input size. It iterates over the input list and places each number in its appropriate bin based on the value of the selected digit. Finally, it recursively calls itself to sort each bin and combines the sorted bins into a single sorted list.

#python2.6 <
from math import log
 
def getDigit(num, base, digit_num):
    # pulls the selected digit
    return (num // base ** digit_num) % base  
 
def makeBlanks(size):
    # create a list of empty lists to hold the split by digit
    return [ [] for i in range(size) ]  
 
def split(a_list, base, digit_num):
    buckets = makeBlanks(base)
    for num in a_list:
        # append the number to the list selected by the digit
        buckets[getDigit(num, base, digit_num)].append(num)  
    return buckets
 
# concatenate the lists back in order for the next step
def merge(a_list):
    new_list = []
    for sublist in a_list:
       new_list.extend(sublist)
    return new_list
 
def maxAbs(a_list):
    # largest abs value element of a list
    return max(abs(num) for num in a_list)

def split_by_sign(a_list):
    # splits values by sign - negative values go to the first bucket,
    # non-negative ones into the second
    buckets = [[], []]
    for num in a_list:
        if num < 0:
            buckets[0].append(num)
        else:
            buckets[1].append(num)
    return buckets
 
def radixSort(a_list, base):
    # there are as many passes as there are digits in the longest number
    passes = int(round(log(maxAbs(a_list), base)) + 1) 
    new_list = list(a_list)
    for digit_num in range(passes):
        new_list = merge(split(new_list, base, digit_num))
    return merge(split_by_sign(new_list))


#python3.7 <
def flatten(some_list):
    """
    Flatten a list of lists.
    Usage: flatten([[list a], [list b], ...])
    Output: [elements of list a, elements of list b]
    """
    new_list = []
    for sub_list in some_list:
        new_list += sub_list
    return new_list

def radix(some_list, idex=None, size=None):
    """
    Recursive radix sort
    Usage: radix([unsorted list])
    Output: [sorted list]
    """
    # Initialize variables not set in the initial call
    if size == None:
        largest_num = max(some_list)
        largest_num_str = str(largest_num)
        largest_num_len = len(largest_num_str)
        size = largest_num_len

    if idex == None:
        idex = size

    # Translate the index we're looking at into an array index.
    # e.g., looking at the 10's place for 100:
    # size: 3
    # idex: 2
    #    i: (3-2) == 1
    # str(123)[i] -> 2
    i = size - idex 

    # The recursive base case.
    # Hint: out of range indexing errors
    if i >= size:
        return some_list

    # Initialize the bins we will place numbers into
    bins = [[] for _ in range(10)]

    # Iterate over the list of numbers we are given
    for e in some_list:
        # The destination bin; e.g.,:
        #   size: 5
        #      e: 29
        #  num_s: '00029'
        #      i: 3
        # dest_c: '2'
        # dest_i: 2
        num_s  = str(e).zfill(size)
        dest_c = num_s[i]
        dest_i = int(dest_c) 
        bins[dest_i] += [e]

    result = []
    for b in bins:
        #If the bin is empty it skips the recursive call
        if b == []:
            continue
        # Make the recursive call
        # Sort each of the sub-lists in our bins
        result.append(radix(b, idex-1, size))

    # Flatten our list
    # This is also called in our recursive call,
    # so we don't need flatten to be recursive.
    flattened_result = flatten(result)

    return flattened_result


#python3.7 <
def flatten(l):
    return [y for x in l for y in x]

def radix(l, p=None, s=None):
    if s == None:
        s = len(str(max(l)))
    if p == None:
        p = s

    i = s - p

    if i >= s:
        return l

    bins = [[] for _ in range(10)]

    for e in l:
        bins[int(str(e).zfill(s)[i])] += [e]

    return flatten([radix(b, p-1, s) for b in bins])