Explanation

• Concept: Radix sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It processes digits from the least significant to the most significant (LSD) or vice versa (MSD).
• Process: Radix sort processes each digit of the numbers, grouping them into buckets based on the current digit, and then concatenates the buckets.
• Steps:
  • Determine the maximum number of digits in the largest number.
  • For each digit, from the least significant to the most significant:
  • Group the numbers into buckets based on the current digit.
  • Concatenate the buckets to form the new order of numbers.
• Efficiency: Radix sort has a time complexity of O(d*(n+b)), where d is the number of digits, n is the number of elements, and b is the base of the number system. It is efficient for large datasets with a fixed number of digits.

Python Implementation

      
          from typing import List

def counting_sort(arr: List[int], exp: int) -> List[int]:
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

    return arr

def radix_sort(arr: List[int]) -> List[int]:
    if not arr:
        return arr
    max1 = max(arr)
    exp = 1
    while max1 // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    sorted_arr = radix_sort(arr)
    print("Sorted array:", sorted_arr)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Random Order

  Input:

  • Array: [170, 45, 75, 90, 802, 24, 2, 66]
  • Target:

  Expected Output: [2, 24, 45, 66, 75, 90, 170, 802]

  Explanation: The input array [170, 45, 75, 90, 802, 24, 2, 66] is sorted in ascending order.

• Already Sorted

  Input:

  • Array: [2, 24, 45, 66, 75, 90, 170, 802]
  • Target:

  Expected Output: [2, 24, 45, 66, 75, 90, 170, 802]

  Explanation: The input array is already sorted, so the output remains the same.

• Reverse Order

  Input:

  • Array: [802, 170, 90, 75, 66, 45, 24, 2]
  • Target:

  Expected Output: [2, 24, 45, 66, 75, 90, 170, 802]

  Explanation: The input array [802, 170, 90, 75, 66, 45, 24, 2] is sorted in ascending order.

• Single Element

  Input:

  • Array: [42]
  • Target:

  Expected Output: [42]

  Explanation: A single element array is already sorted.

• Empty Array

  Input:

  • Array: []
  • Target:

  Expected Output: []

  Explanation: An empty array remains empty after sorting.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"input": [170, 45, 75, 90, 802, 24, 2, 66], "expected": [2, 24, 45, 66, 75, 90, 170, 802]},
        {"input": [2, 24, 45, 66, 75, 90, 170, 802], "expected": [2, 24, 45, 66, 75, 90, 170, 802]},
        {"input": [802, 170, 90, 75, 66, 45, 24, 2], "expected": [2, 24, 45, 66, 75, 90, 170, 802]},
        {"input": [42], "expected": [42]},
        {"input": [], "expected": []},
    ]
    for i, test in enumerate(tests, 1):
        result = radix_sort(test["input"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")
if __name__ == "__main__":
    run_tests()