Counting Sort (काउंटिंग सॉर्ट)
एल्गोरिदम जैसे Merge Sort किसी दिए गए अनुक्रम को क्रमबद्ध करने के लिए आम तौर पर ऑपरेशन्स करते हैं। ज़्यादातर प्रोग्रामिंग भाषाओं में मौजूद बिल्ट-इन
sort() फ़ंक्शन भी लगभग ऑपरेशन्स ही इस्तेमाल करते हैं। ऐसे में एक स्वाभाविक प्रश्न उठता है—क्या इससे भी तेज़ कोई सॉर्टिंग तरीका हो सकता है?एक बेसिक एल्गोरिदम जो समय में किसी लिस्ट को सॉर्ट कर सकता है, वह है Counting Sort (काउंटिंग सॉर्ट)। यह एक प्रभावी, रैखिक समय (linear-time) एल्गोरिदम है, जो तब विशेष रूप से उपयोगी होता है, जब हमारे पास छोटे तथा सीमित integer मानों वाली लिस्ट हो।
Counting Sort का मूल विचार यह है कि हम इनपुट में मौजूद विभिन्न मानों की आवृत्ति (frequency) गिनने के लिए एक हिस्टोग्राम जैसी संरचना का उपयोग करते हैं, और फिर उसी जानकारी का उपयोग करके इनपुट सूची को क्रमबद्ध क्रम (sorted order) में पुनर्व्यवस्थित करते हैं।
उदाहरण के लिए, यदि हमें इस ऐरे को सॉर्ट करना हो:
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], तो हम एक हिस्टोग्राम बनाएँगे जहाँ पता चलेगा कि 1 कुल 6 बार है, 2 कुल 2 बार है, 3 कुल 5 बार है, वगैरह। यह हिस्टोग्राम [6, 2, 5, 4, 5, 1, 6, 1] जैसा दिखेगा (जैसा कि चित्र में दर्शाया गया है)।
a = ...
bottom, top = min(a), max(a) + 1 # श्रेणी निर्धारित करें
hist = [0] * (top - bottom) # श्रेणी में 0 से भरें => कोई गिनती नहीं
for num in a: # ऐरे में पुनरावृत्ति करें
hist[num - bottom] += 1 # हिस्टोग्राम मान बढ़ाएँ
res = [] # परिणाम ऐरे को आरंभ करें
for num in range(bottom, top): # श्रेणी में पुनरावृत्ति करें
res += [num] * hist[num - bottom] # हिस्टोग्राम में मौजूद मान के अनुसार उतने num परिणाम में जोड़ेंअंत में, परिणामी ऐरे इस प्रकार होगा:
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8]।ध्यान दें कि यह तरीक़ा सिर्फ़ संख्याओं (ख़ासकर छोटी रेंज की संख्याओं) पर काम करता है, जबकि Bubble Sort या Merge Sort जैसे अन्य एल्गोरिदम किसी भी प्रकार के तत्वों पर काम कर सकते हैं, बशर्ते उन तत्वों की आपस में तुलना की जा सके।
इस एल्गोरिदम में कुल ऑपरेशन्स लगते हैं, जहाँ
n इनपुट ऐरे में तत्वों की संख्या है और r उन संख्यात्मक मानों की रेंज का आकार है। जब संख्याओं की रेंज छोटी होती है, तब यह Merge Sort जैसे एल्गोरिदम की तुलना में तेज़ साबित हो सकता है।🤔
क्या सॉर्टिंग के लिए अन्य रैखिक समय (linear-time) एल्गोरिदम मौजूद हैं?
हाँ, आप Radix-sort पर नज़र डाल सकते हैं। हालाँकि, ये भी केवल संख्याओं पर ही काम करते हैं।
यदि हम सिर्फ़ comparison-based एल्गोरिदम लें, जो किसी भी प्रकार की लिस्ट पर काम कर सकते हैं (बशर्ते हमें सिर्फ़ तत्वों के बीच तुलना करनी हो), तो सबसे बेहतरीन एल्गोरिदम भी से तेज़ नहीं हो सकते।
इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n होता है (1 ≤ n ≤ )।अगली पंक्ति में
n अंतराल से अलग किए गए पूर्णांक होते हैं (-100 ≤ ≤ 100)।आउटपुट
कार्यक्रम को इन्हीं
n पूर्णांकों को बढ़ते हुए क्रम में स्पेस द्वारा अलग करके प्रिंट करना चाहिए।उदाहरण
इनपुट | आउटपुट |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB