काउंटिंग सॉर्ट

काउंटिंग सॉर्ट मानों की तुलना करके सॉर्ट करता ही नहीं। अगर आप जानते हैं कि हर मान, मान लीजिए, 1 से 40 के बीच की पूर्ण संख्या है, तो आप बस गिन सकते हैं कि हर मान कितनी बार है, और गिनतियों से निकाल सकते हैं कि हर मान कहाँ जाएगा। छोटी रेंज के लिए सॉर्टिंग इससे ज़्यादा तेज़ मुश्किल से हो सकती है।

एक सूची के बार, हर मान कितनी बार आता है यह दिखाती काउंटरों की पट्टी, और एक बफ़र पंक्ति जिसमें हर मान का अपना खंड है
एक सूची के बार, हर मान कितनी बार आता है यह दिखाती काउंटरों की पट्टी, और एक बफ़र पंक्ति जिसमें हर मान का अपना खंड है

गिनें

सबसे छोटा और सबसे बड़ा मान ढूँढें और उनके बीच हर मान के लिए एक काउंटर बनाएँ, सब शून्य से शुरू। सूची को शुरू से अंत तक एक बार पढ़ें और जो भी मान दिखे, उसके काउंटर में एक जोड़ें। अब काउंटर एक हिस्टोग्राम बनाते हैं: कितने 1, कितने 2, और इसी तरह आगे। n मानों और k काउंटरों के साथ इसमें n चरण लगते हैं।

जोड़ें

सबसे छोटे मान के बराबर वाले मान सबसे पहले आते हैं, इसलिए उनका खंड जगह 1 से शुरू होता है। अगले मान का खंड उनके ठीक बाद शुरू होता है, और इसी तरह आगे: हर खंड अपने से पहले की सभी गिनतियों के योग के बाद शुरू होता है। ये चालू योग, जिन्हें प्रीफ़िक्स योग कहते हैं, हिस्टोग्राम को सॉर्ट की हुई सूची के नक़्शे में बदल देते हैं। इसमें k चरण लगते हैं।

रखें

सूची को दूसरी बार पढ़ें और हर मान को उसके खंड की अगली ख़ाली जगह पर ले जाएँ। चूँकि मान उसी क्रम में ले जाए जाते हैं जिसमें वे आते हैं, बराबर मानों का मूल क्रम बना रहता है: काउंटिंग सॉर्ट स्थिर है। बफ़र को वापस कॉपी करें, और सूची सॉर्ट हो जाती है। ऐप दिखाता है कि जैसे-जैसे मान रखे जाते हैं, हर काउंटर वापस घटता जाता है।

एक उदाहरण

4, 1, 3, 4, 2, 1, 4 लें। 1 से 4 के काउंटर आख़िर में 2, 1, 1 और 3 पर रुकते हैं। जोड़ने से खंड मिलते हैं: दोनों 1 जगह 1 और 2 पर, 2 जगह 3 पर, 3 जगह 4 पर, और तीनों 4 जगह 5 से 7 पर। मानों को सूची के क्रम में रखने पर 1, 1, 2, 3, 4, 4, 4 मिलता है: 7 मान गिने गए, 14 चालें, 4 काउंटर, और कोई तुलना नहीं।

इसे कब इस्तेमाल करें

कुल काम n + k के साथ बढ़ता है। जब k, n की तुलना में छोटा हो, जैसे 0 से 100 तक के एक हज़ार परीक्षा अंक, तो काउंटिंग सॉर्ट किसी भी तुलना-आधारित सॉर्ट से तेज़ है, जिसे लगभग n log₂ n तुलनाएँ चाहिए। जब रेंज बड़ी हो तो यह फ़िज़ूलख़र्च है: दस लाख तक फैले कुछ मानों के लिए दस लाख काउंटर चाहिए। रेडिक्स सॉर्ट इसे हर अंक के लिए एक बार काउंटिंग सॉर्ट चलाकर हल करता है, ताकि हर पास में सिर्फ़ दस काउंटर चाहिए हों। Harold Seward ने 1954 में रेडिक्स सॉर्ट के साथ काउंटिंग सॉर्ट का वर्णन किया।

ख़ुद आज़माएँ

ऐप खोलें और आगे दबाएँ। सूची और बफ़र पंक्ति के बीच की पट्टी हर मान के लिए एक काउंटर दिखाती है। देखें कि सूची पढ़ते समय काउंटर कैसे भरते हैं, गिनतियाँ जोड़ने पर बफ़र में खंड कैसे दिखते हैं, और मान रखे जाने पर काउंटर कैसे वापस घटते हैं। बड़े खंड देखने के लिए कुछ ही अलग मान चुनें, या एक-दूसरे से दूर की संख्याएँ लिखकर देखें कि बड़ी रेंज को कितने काउंटर चाहिए।

अक्सर पूछे जाने वाले प्रश्न

काउंटिंग सॉर्ट की समय जटिलता क्या है?

n मानों और k संभावित मानों के लिए O(n + k), और काउंटरों व बफ़र के लिए O(n + k) अतिरिक्त मेमोरी।

काउंटिंग सॉर्ट हमेशा सबसे तेज़ क्यों नहीं होता?

क्योंकि इसकी लागत मानों की रेंज पर निर्भर करती है, सिर्फ़ उनकी संख्या पर नहीं। अगर रेंज सूची से बहुत बड़ी हो, तो ज़्यादातर काउंटर शून्य पर ही रहते हैं और समय व मेमोरी बर्बाद होते हैं।

क्या काउंटिंग सॉर्ट ऋणात्मक संख्याएँ संभाल सकता है?

हाँ। काउंटर सबसे छोटे मान से सबसे बड़े तक चलते हैं, इसलिए काउंटर का इंडेक्स पाने के लिए सबसे छोटा मान घटा दें। ऐप भी यही करता है।

क्या काउंटिंग सॉर्ट स्थिर है?

हाँ, बशर्ते मानों को सूची के क्रम में उनके खंड की अगली ख़ाली जगह पर ले जाया जाए। रेडिक्स सॉर्ट इसी पर निर्भर है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

काउंटिंग सॉर्ट आज़माएँ