Radix Sort

 Radix Sort

Radix sort is a non-comparative sorting algorithm that sorts elements by comparing their digits (or radix) in different positions. It can be used to sort strings, integers, and other types of data.

python

# Radix sort function

def radix_sort(lst):

    max_num = max(lst)

    exp = 1

    while max_num // exp > 0:

        counting_sort(lst, exp)

        exp *= 10

def counting_sort(lst, exp):

    n = len(lst)

    output = [0] * n

    count = [0] * 10

    for i in range(n):

        index = lst[i] // exp

        count[index % 10] += 1

    for i in range(1, 10):

        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):

        index = lst[i] // exp

        output[count[index % 10] - 1] = lst[i]

        count[index % 10] -= 1

    for i in range(n):

        lst[i] = output[i]