Counting Sort — வயது, மதிப்பெண், histogram

Counting sort ஒப்பீடு சார்ந்த வரிசை அல்ல; அதிர்வெண்ணை எண்ணி, பிறகு அந்த எண்ணிக்கைகளின் அடிப்படையில் வெளியீட்டை உருவாக்குகிறது. மதிப்புகள் சிறிய முழு எண் வரம்பில் இருக்கும்போது (0–100 மதிப்பெண் போல) இது மிகவும் பொருத்தமானது.

உண்மை உலகில் இது ஏன் முக்கியம்?

தேர்தல் அலுவலகம் ஒவ்வொரு வாக்கும் சிறிய வேட்பாளர் குறியீடு என்றால், ஒவ்வொரு குறியீட்டுக்கும் எண்ணி வரிசைப்படுத்தலாம். உணரி (sensor) மட்டும் {0,1,2,3} தீவிரம் அனுப்பினால், ஒவ்வொரு மதிப்பின் எண்ணிக்கையை எண்ணி O(n+k) பாணியில் வரிசைப்படுத்தலாம். நினைவக சிக்கல்: உதவி அணி k = (max−min+1) அளவுக்கு தேவை; பரந்த மற்றும் அரிதான மதிப்புகளுக்கு இது பொருந்தாது.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

முதல் கட்டம்: min முதல் max வரை எண்ணிக்கை அணி. உள்ளீட்டை ஒருமுறை நடத்தி எண்ணிக்கையை அதிகரிக்கவும். இரண்டாம் கட்டம்: r குறைந்ததிலிருந்து அதிகமாக நடந்து, ஒவ்வொரு r-ஐ count[r] முறை வெளியீட்டில் எழுதவும். O(n+k) நேரம். நிலைத்தன்மை: prefix sum + பின்னோக்கி நிரப்புதல். இது ஒப்பீட்டு வரிசை அல்ல என்பதால் Ω(n log n) வரம்பை மீற முடியும்.

Pythonில் முயற்சி செய்வோம்

def counting_sort(values: list[int]) -> list[int]:
    if not values:
        return []
    lo, hi = min(values), max(values)
    k = hi - lo + 1
    count = [0] * k
    for v in values:
        count[v - lo] += 1
    out: list[int] = []
    for i, c in enumerate(count):
        out.extend([lo + i] * c)
    return out


print(counting_sort([3, 0, 2, 3, 2]))

அடிக்கடி நேரும் தவறுகள்

• k மிகப் பெரியது என்றால் நினைவகம் வெடிக்கும்.
• [min,max] எல்லையில் ஒற்றைப் பிழை.
• நகல்களின் உள்ளீட்டு வரிசையைப் பாதுகாக்க வேண்டுமானால், மீண்டும் கட்டுமான வரிசையைத் தவறவிடுவது.

முக்கியச் சுருக்கக் குறிப்புகள்

• k சிறியது எனில் O(n+k) நேரம், பொதுவாக O(k) கூடுதல் இடம்.
• வரம்பிட்ட சிறிய முழு எண்கள்; மப்பிங் இல்லாமல் சாதாரண சரங்களுக்கு அல்ல.
• Radix sort உடன் தொடர்பு: இலக்கு திரும்ப திரும்ப counting sort பயன்படும்.