Day 75: Python Counting Sort by Zeros – Stable O(n) Custom Key Sort for Digit Counts (Algo Mastery)

#challenge #python #algorithms #datastructures

Welcome to Day 75 of the #80DaysOfChallenges journey! This intermediate challenge implements sorting numbers based on zero digit count using counting sort principles, where numbers with fewer zeros come first, leveraging buckets for O(n) time when key range (max zeros) is small. It combines digit counting via string, dict for bucketing, and sorted keys for stable output, a non-comparison sort pattern for bounded keys like ratings or ages. If you're advancing from basic sorts to stable bucket sorts or handling custom criteria, this "Python sort by zeros" script demonstrates a function that's efficient, preserves order within buckets, and easy to adapt for other digit-based keys.

💡 Key Takeaways from Day 75: Counting Sort Function

This task features a helper for zero count and main function with dict buckets, sorted keys for append. It's a counting sort variant: bucket by key, sort buckets, concatenate. We'll detail: zero count helper with string, bucketing with dict and extend, and main with input parse.

1. Zero Count Helper: String-Based Digit Count

The count_zeros function counts '0's in n:

def count_zeros(n: int) -> int:
    """Return number of '0' digits in the integer."""
    return str(n).count("0")

Converts to str, uses count for '0'. Simple, handles 0 as 1, negatives not (assume positive). O(d) d digits.

2. Sorting Function: Dict Buckets and Sorted Keys

The counting_sort_by_zeros buckets by zero count:

def counting_sort_by_zeros(nums: list[int]) -> list[int]:
    """Sort numbers by the count of zeros using counting sort."""
    buckets = {}                      # map zero-count -> list of numbers

    for num in nums:
        z = count_zeros(num)          # count zeros in current number
        if z not in buckets:
            buckets[z] = []
        buckets[z].append(num)        # place number in its bucket

    result = []

    for z in sorted(buckets.keys()):  # iterate in increasing zero-count order
        result.extend(buckets[z])     # append numbers in each bucket

    return result

Dict buckets collect by z. Sorted keys ensure fewer zeros first. Extend preserves original order within count (stable). O(n + r log r) r max zeros (small).

3. Main Interactive: Space-Separated Input

Script reads nums, calls, prints:

raw = input("Enter numbers (space-separated): ").strip()
nums = list(map(int, raw.split()))

sorted_nums = counting_sort_by_zeros(nums)
print(f"Sorted by zero count: {sorted_nums}")