Radix Sort Algorithm

def radix_sort_detailed(arr):
    """Radix Sort with detailed steps"""
    if not arr:
        return arr
    
    print(f"Starting array: {arr}")
    
    # Find maximum number to know number of digits
    max_num = max(arr)
    max_digits = len(str(max_num))
    print(f"Maximum number: {max_num} (has {max_digits} digits)")
    
    # Do counting sort for every digit position
    exp = 1
    digit_position = 1
    
    while max_num // exp > 0:
        print(f"\n--- Sorting by digit position {digit_position} (exp = {exp}) ---")
        
        # Show what digit we're looking at for each number
        print("Digits being sorted:")
        for num in arr:
            digit = (num // exp) % 10
            print(f"  {num:3d} -> digit {digit}")
        
        # Perform counting sort by current digit
        counting_sort_by_digit_detailed(arr, exp)
        
        print(f"After sorting by position {digit_position}: {arr}")
        
        exp *= 10
        digit_position += 1
    
    print(f"\nFinal sorted array: {arr}")
    return arr

def counting_sort_by_digit_detailed(arr, exp):
    """Counting sort by specific digit position with details"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 10 digits (0-9)
    
    # Count occurrences of each digit
    print("  Counting digits:")
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1
        print(f"    {arr[i]} has digit {digit}, count[{digit}] = {count[digit]}")
    
    print(f"  Count array: {count}")
    
    # Change count[i] to actual position of this digit in output
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    print(f"  Position array: {count}")
    
    # Build output array (process from right to left for stability)
    print("  Building output:")
    i = n - 1
    while i >= 0:
        digit = (arr[i] // exp) % 10
        position = count[digit] - 1
        output[position] = arr[i]
        print(f"    {arr[i]} (digit {digit}) goes to position {position}")
        count[digit] -= 1
        i -= 1
    
    # Copy output array back to arr
    for i in range(n):
        arr[i] = output[i]

# Example usage
numbers = [170, 45, 75, 90, 2, 802, 24, 66]
print("=== Radix Sort Step by Step ===")
sorted_numbers = radix_sort_detailed(numbers.copy())

def radix_sort(arr):
    """
    Simple Radix Sort implementation
    Time Complexity: O(d × n) where d is number of digits
    Space Complexity: O(n + k) where k is range of digits (10)
    """
    if not arr:
        return arr
    
    # Find the maximum number to know number of digits
    max_num = max(arr)
    
    # Do counting sort for every digit
    # Start with least significant digit (exp = 1)
    exp = 1
    while max_num // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10  # Move to next digit position
    
    return arr

def counting_sort_by_digit(arr, exp):
    """
    Counting sort based on the digit represented by exp
    exp = 1 for units place, 10 for tens place, 100 for hundreds, etc.
    """
    n = len(arr)
    output = [0] * n  # Output array
    count = [0] * 10  # Count array for digits 0-9
    
    # Store count of occurrences of each digit
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1
    
    # Change count[i] so it contains actual position of digit in output
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build the output array
    # Process elements from right to left to maintain stability
    i = n - 1
    while i >= 0:
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
        i -= 1
    
    # Copy the output array to arr, so arr contains sorted numbers
    for i in range(n):
        arr[i] = output[i]

# Test the function
test_array = [170, 45, 75, 90, 2, 802, 24, 66]
print("Original array:", test_array)
sorted_array = radix_sort(test_array.copy())
print("Sorted array:", sorted_array)

🔹Radix Sort with Different Base

def radix_sort_base(arr, base=10):
    """Radix sort with configurable base (default base 10)"""
    if not arr:
        return arr
    
    max_num = max(arr)
    
    exp = 1
    while max_num // exp > 0:
        counting_sort_by_digit_base(arr, exp, base)
        exp *= base
    
    return arr

def counting_sort_by_digit_base(arr, exp, base):
    """Counting sort for specific base"""
    n = len(arr)
    output = [0] * n
    count = [0] * base
    
    # Count occurrences
    for i in range(n):
        digit = (arr[i] // exp) % base
        count[digit] += 1
    
    # Calculate positions
    for i in range(1, base):
        count[i] += count[i - 1]
    
    # Build output
    i = n - 1
    while i >= 0:
        digit = (arr[i] // exp) % base
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
        i -= 1
    
    # Copy back
    for i in range(n):
        arr[i] = output[i]

# Example with different bases
numbers = [64, 34, 25, 12, 22, 11, 90]
print("Original:", numbers)
print("Base 10:", radix_sort_base(numbers.copy(), 10))
print("Base 2:", radix_sort_base(numbers.copy(), 2))
print("Base 16:", radix_sort_base(numbers.copy(), 16))

🔹Radix Sort for Strings

def radix_sort_strings(arr):
    """Radix sort for strings of equal length"""
    if not arr or not arr[0]:
        return arr
    
    # All strings must have the same length
    max_length = len(arr[0])
    
    # Sort by each character position from right to left
    for pos in range(max_length - 1, -1, -1):
        counting_sort_by_char(arr, pos)
    
    return arr

def counting_sort_by_char(arr, pos):
    """Counting sort by character at specific position"""
    n = len(arr)
    output = [''] * n
    count = [0] * 256  # ASCII characters
    
    # Count occurrences
    for i in range(n):
        char_code = ord(arr[i][pos]) if pos < len(arr[i]) else 0
        count[char_code] += 1
    
    # Calculate positions
    for i in range(1, 256):
        count[i] += count[i - 1]
    
    # Build output
    i = n - 1
    while i >= 0:
        char_code = ord(arr[i][pos]) if pos < len(arr[i]) else 0
        output[count[char_code] - 1] = arr[i]
        count[char_code] -= 1
        i -= 1
    
    # Copy back
    for i in range(n):
        arr[i] = output[i]

# Example with strings
words = ["cat", "dog", "rat", "bat", "hat", "mat"]
print("Original strings:", words)
print("Sorted strings:", radix_sort_strings(words.copy()))

🔹MSD (Most Significant Digit) Radix Sort

def msd_radix_sort(arr, digit_pos=None):
    """
    Most Significant Digit Radix Sort
    Sorts from left to right (most significant digit first)
    """
    if not arr:
        return arr
    
    if digit_pos is None:
        # Find the maximum number of digits
        max_num = max(arr)
        digit_pos = len(str(max_num)) - 1
    
    if digit_pos < 0:
        return arr
    
    # Create buckets for each digit (0-9)
    buckets = [[] for _ in range(10)]
    
    # Distribute numbers into buckets based on current digit
    for num in arr:
        digit = get_digit_at_position(num, digit_pos)
        buckets[digit].append(num)
    
    # Recursively sort each bucket and concatenate
    result = []
    for bucket in buckets:
        if len(bucket) > 1:
            # Recursively sort bucket by next digit position
            sorted_bucket = msd_radix_sort(bucket, digit_pos - 1)
            result.extend(sorted_bucket)
        else:
            result.extend(bucket)
    
    return result

def get_digit_at_position(num, pos):
    """Get digit at specific position (0 = rightmost)"""
    return (num // (10 ** pos)) % 10

# Example
numbers = [170, 45, 75, 90, 2, 802, 24, 66]
print("Original:", numbers)
print("MSD Radix Sort:", msd_radix_sort(numbers.copy()))

🔹Radix Sort with Negative Numbers

def radix_sort_with_negatives(arr):
    """Radix sort that handles negative numbers"""
    if not arr:
        return arr
    
    # Separate positive and negative numbers
    positive = [x for x in arr if x >= 0]
    negative = [-x for x in arr if x < 0]  # Make positive for sorting
    
    # Sort positive numbers normally
    if positive:
        radix_sort(positive)
    
    # Sort negative numbers (as positive) then reverse and negate
    if negative:
        radix_sort(negative)
        negative = [-x for x in reversed(negative)]
    
    # Combine: negatives first, then positives
    return negative + positive

# Example with negative numbers
mixed_numbers = [170, -45, 75, -90, 2, -802, 24, 66]
print("Original with negatives:", mixed_numbers)
print("Sorted with negatives:", radix_sort_with_negatives(mixed_numbers.copy()))

import time
import random
import math

def analyze_radix_sort_performance():
    """Analyze Radix Sort performance characteristics"""
    
    def quick_sort(arr):
        """Quick sort for comparison"""
        if len(arr) <= 1:
            return arr
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)
    
    def measure_time(sort_func, arr):
        start = time.time()
        sort_func(arr.copy())
        return (time.time() - start) * 1000
    
    print("=== Radix Sort vs Quick Sort Performance ===")
    print(f"{'Scenario':25} | {'Size':>6} | {'Digits':>6} | {'Radix':>8} | {'Quick':>8} | {'Winner':>8}")
    print("-" * 75)
    
    scenarios = [
        ("Small numbers", 10000, 2),      # 0-99
        ("Medium numbers", 10000, 3),     # 0-999
        ("Large numbers", 10000, 6),      # 0-999999
        ("Very large numbers", 10000, 9), # 0-999999999
        ("Small dataset", 100, 6),        # Small n, large digits
        ("Large dataset", 100000, 3),     # Large n, small digits
    ]
    
    for scenario_name, n, max_digits in scenarios:
        # Generate test data
        max_val = 10 ** max_digits - 1
        test_data = [random.randint(0, max_val) for _ in range(n)]
        
        # Measure both algorithms
        radix_time = measure_time(radix_sort, test_data)
        quick_time = measure_time(quick_sort, test_data)
        
        winner = "Radix" if radix_time < quick_time else "Quick"
        
        print(f"{scenario_name:25} | {n:6d} | {max_digits:6d} | {radix_time:6.2f}ms | {quick_time:6.2f}ms | {winner:>8}")

def complexity_analysis():
    """Analyze time complexity in practice"""
    
    def count_operations_radix(arr):
        """Count operations in radix sort"""
        if not arr:
            return 0, 0
        
        max_num = max(arr)
        digits = len(str(max_num))
        n = len(arr)
        
        # Each digit requires O(n) operations for counting sort
        # Total: O(d * n) where d is number of digits
        operations = digits * n * 3  # Approximate: count, position, copy
        
        return operations, digits
    
    print("\n=== Complexity Analysis ===")
    print(f"{'Array Size':>10} | {'Max Value':>10} | {'Digits':>6} | {'Operations':>12} | {'O(n log n)':>12} | {'Ratio':>8}")
    print("-" * 75)
    
    test_cases = [
        (1000, 999),        # 3 digits
        (1000, 9999),       # 4 digits
        (1000, 99999),      # 5 digits
        (10000, 999),       # Large n, small digits
        (10000, 999999),    # Large n, large digits
    ]
    
    for n, max_val in test_cases:
        test_data = [random.randint(0, max_val) for _ in range(n)]
        
        operations, digits = count_operations_radix(test_data)
        comparison_ops = n * math.log2(n)  # O(n log n)
        ratio = operations / comparison_ops
        
        print(f"{n:10d} | {max_val:10d} | {digits:6d} | {operations:12.0f} | {comparison_ops:12.0f} | {ratio:6.2f}")

def memory_analysis():
    """Analyze memory usage"""
    import sys
    
    print("\n=== Memory Usage Analysis ===")
    print(f"{'Array Size':>10} | {'Input Memory':>12} | {'Extra Memory':>12} | {'Total Memory':>12} | {'Efficiency':>12}")
    print("-" * 75)
    
    sizes = [100, 1000, 10000, 100000]
    
    for n in sizes:
        # Memory for input array
        input_memory = n * 4  # 4 bytes per integer
        
        # Extra memory for radix sort:
        # - Output array: n integers
        # - Count array: 10 integers (for digits 0-9)
        extra_memory = (n + 10) * 4
        
        total_memory = input_memory + extra_memory
        efficiency = "Good" if extra_memory <= input_memory else "Moderate"
        
        print(f"{n:10d} | {input_memory:10d}B | {extra_memory:10d}B | {total_memory:10d}B | {efficiency:>12}")

def digit_distribution_impact():
    """Analyze impact of digit distribution"""
    
    print("\n=== Impact of Number of Digits ===")
    print(f"{'Max Digits':>10} | {'Array Size':>10} | {'Time (ms)':>10} | {'Time per Digit':>15}")
    print("-" * 50)
    
    n = 10000
    digit_ranges = [1, 2, 3, 4, 5, 6]
    
    for max_digits in digit_ranges:
        max_val = 10 ** max_digits - 1
        test_data = [random.randint(0, max_val) for _ in range(n)]
        
        start_time = time.time()
        radix_sort(test_data.copy())
        total_time = (time.time() - start_time) * 1000
        
        time_per_digit = total_time / max_digits
        
        print(f"{max_digits:10d} | {n:10d} | {total_time:8.2f} | {time_per_digit:13.2f}")

# Run all analyses
analyze_radix_sort_performance()
complexity_analysis()
memory_analysis()
digit_distribution_impact()

def radix_sort_numbers(numbers):
    """Simple Radix Sort for phone numbers"""
    # Find the maximum number to know number of digits
    max_num = max(numbers)
    
    # Do counting sort for every digit position
    exp = 1  # Start with rightmost digit
    while max_num // exp > 0:
        # Create output array and count array
        output = [0] * len(numbers)
        count = [0] * 10
        
        # Count occurrences of each digit
        for num in numbers:
            digit = (num // exp) % 10
            count[digit] += 1
        
        # Update count array to get actual positions
        for i in range(1, 10):
            count[i] += count[i - 1]
        
        # Build the output array
        for i in range(len(numbers) - 1, -1, -1):
            digit = (numbers[i] // exp) % 10
            output[count[digit] - 1] = numbers[i]
            count[digit] -= 1
        
        # Copy output array to numbers
        for i in range(len(numbers)):
            numbers[i] = output[i]
        
        exp *= 10  # Move to next digit
    
    return numbers

def main():
    # Sample phone numbers (without area code for simplicity)
    phone_numbers = [5551234, 5559876, 5552468, 5551357, 5553579, 5557531]
    
    print("Original phone numbers:")
    for num in phone_numbers:
        print(f"  {num}")
    
    # Sort the phone numbers
    sorted_numbers = radix_sort_numbers(phone_numbers.copy())
    
    print("\n📱 Sorted phone numbers:")
    for num in sorted_numbers:
        print(f"  {num}")

# Run the program
if __name__ == "__main__":
    main()