गिनती क्रम
| Class | सॉर्टिंग कलन विधि |
|---|---|
| Data structure | सरणी |
| Worst-case performance | , जहां k गैर-नकारात्मक कुंजी मानों की सीमा है। |
| Worst-case space complexity |
अभिकलित्र विज्ञान में, काउंटिंग सॉर्ट, छोटे सकारात्मक पूर्णांक वाली कुंजियों के अनुसार वस्तुओं के संग्रह को सॉर्ट करने के लिए एक कलन विधि है; अर्थात्, यह एक पूर्णांक प्रवरण कलन विधि है। यह उन वस्तुओं की संख्या की गणना करके संचालित होता है जिनमें अलग-अलग कुंजी मान होते हैं, और आउटपुट अनुक्रम में प्रत्येक कुंजी मान की स्थिति निर्धारित करने के लिए उन गणनाओं पर उपसर्ग योग लागू करते हैं। इसका चलने का समय वस्तुओं की संख्या और अधिकतम कुंजी मान और न्यूनतम कुंजी मान के बीच अंतर में रैखिक है, इसलिए यह केवल उन स्थितियों में सीधे उपयोग के लिए उपयुक्त है जहां कुंजियों में भिन्नता वस्तुओं की संख्या से काफी अधिक नहीं है। इसे अधिकांशत: एक सबरूटीन के रूप में उपयोग किया जाता है, यह एक अन्य प्रवरण कलन विधि है, जो बड़ी कुंजियों को अधिक कुशलता से संभाल सकता है।[1][2][3] गिनती का प्रकार तुलनात्मक प्रकार नहीं है; यह किसी सरणी में अनुक्रमणिका के रूप में मुख्य मानों का उपयोग करता है Ω(n log n) तुलना प्रवरण के लिए निचली सीमा लागू नहीं होगी।[1] बकट सॉर्ट का उपयोग गिनती सॉर्ट के बदले में किया जा सकता है, और इसमें समान समय विश्लेषण सम्मलित होता है। चूंकि, काउंटिंग सॉर्ट की तुलना में, बकेट सॉर्ट के लिए प्रत्येक बकेट के भीतर वस्तुओं के सेट को रखने के लिए लिंक की गई सूचियों, गतिशील सरणियों या पूर्व-आवंटित मेमोरी की एक बड़ी मात्रा की आवश्यकता होती है, जबकि काउंटिंग सॉर्ट प्रति बकट एक एकल संख्या (आइटमों की गिनती) को संग्रहीत करता है। .[4]
इनपुट और आउटपुट धारणाएँ
सबसे सामान्य स्थितिे में, काउंटिंग सॉर्ट के इनपुट में n आइटमों का एक संग्रह होता है, जिनमें से प्रत्येक में एक गैर-नकारात्मक पूर्णांक कुंजी होती है जिसका अधिकतम मान अधिकतम k होता है। [3]गिनती क्रम के कुछ विवरणों में, क्रमबद्ध किए जाने वाले इनपुट को पूर्णांकों का एक अनुक्रम मात्र माना जाता है,[1]लेकिन यह सरलीकरण गिनती के कई अनुप्रयोगों को समायोजित नहीं करता है। उदाहरण के लिए, जब रेडिक्स सॉर्ट में एक सबरूटीन के रूप में उपयोग किया जाता है, तो प्रत्येक कॉल के लिए काउंटिंग सॉर्ट की कुंजियाँ बड़ी आइटम कुंजियों के अलग-अलग अंक होती हैं; केवल आइटमों से अलग किए गए मुख्य अंकों की क्रमबद्ध सूची लौटाना पर्याप्त नहीं होगा।
रेडिक्स सॉर्ट जैसे अनुप्रयोगों में, अधिकतम कुंजी मान पर एक सीमा होती है k पहले से ज्ञात होगा, और इसे कलन विधि के इनपुट का हिस्सा माना जा सकता है। चूंकि, यदि k का मान पहले से ज्ञात नहीं है तो इसकी गणना, पहले चरण के रूप में, अधिकतम कुंजी मान निर्धारित करने के लिए डेटा पर एक अतिरिक्त लूप द्वारा की जा सकती है।
आउटपुट उनकी कुंजियों द्वारा क्रमित तत्वों की एक ऐरे डेटा संरचना है। रेडिक्स प्रवरण के लिए इसके अनुप्रयोग के कारण, गिनती सॉर्ट एक स्थिर सॉर्ट होना चाहिए; अर्थात्, यदि दो तत्व एक ही कुंजी साझा करते हैं, तो आउटपुट सरणी में उनका सापेक्ष क्रम और इनपुट सरणी में उनका सापेक्ष क्रम मेल खाना चाहिए।[1][2]
छद्मकोड
छद्मकोड में, कलन विधि को इस प्रकार व्यक्त किया जा सकता है:
function CountingSort(input, k)
count ← array of k + 1 zeros
output ← array of same length as input
for i = 0 to length(input) - 1 do
j = key(input[i])
count[j] = count[j] + 1
for i = 1 to k do
count[i] = count[i] + count[i - 1]
for i = length(input) - 1 down to 0 do
j = key(input[i])
count[j] = count[j] - 1
output[count[j]] = input[i]
return output
यहाँ input सॉर्ट किया जाने वाला इनपुट ऐरे है, key इनपुट सरणी में प्रत्येक आइटम की संख्यात्मक कुंजी लौटाता है, count एक सहायक सरणी है जिसका उपयोग पहले प्रत्येक कुंजी के साथ आइटमों की संख्या को संग्रहीत करने के लिए किया जाता है, और फिर (दूसरे लूप के बाद) उन स्थितियों को संग्रहीत करने के लिए किया जाता है जहां प्रत्येक कुंजी के साथ आइटम रखे जाने चाहिए,
k गैर-नकारात्मक कुंजी मानों का अधिकतम मान है और output क्रमबद्ध आउटपुट सरणी है।
संक्षेप में, कलन विधि पहले लूप में आइटमों पर लूप करता है, प्रत्येक कुंजी के भीतर होने वाली संख्या के हिस्टोग्राम की गणना करता है input संग्रह, उसके बाद दूसरे लूप में, यह एक उपसर्ग योग गणना करता है count यह निर्धारित करने के लिए, प्रत्येक कुंजी के लिए, वह स्थिति सीमा जहां उस कुंजी वाले आइटम रखे जाने चाहिए; अर्थात कुंजी के आइटम प्रारंभिक स्थिति में रखा जाना चाहिए count[]. अंत में, तीसरे लूप में, यह के आइटम्स पर लूप करता है input फिर से, लेकिन उल्टे क्रम में, प्रत्येक आइटम को उसकी क्रमबद्ध स्थिति में ले जाना output सरणी है।[1][2][3]
समान कुंजियों वाली वस्तुओं का सापेक्ष क्रम यहां संरक्षित है; अर्थात, यह एक :श्रेणी:स्थिर प्रकार है।
जटिलता विश्लेषण
क्योंकि कलन विधि केवल सरल फॉर लूप का उपयोग करता है, रिकर्सन या सबरूटीन कॉल के बिना, इसका विश्लेषण करना सीधा है। गिनती सरणी का आरंभीकरण, और दूसरा लूप के लिए जो गिनती सरणी पर एक उपसर्ग योग करता है, प्रत्येक अधिकतम k + 1 बार पुनरावृत्त होता है और इसलिए O(k) समय लेता है। लूप के लिए अन्य दो, और आउटपुट ऐरे का आरंभीकरण, प्रत्येक O(n) समय लेता है। इसलिए, संपूर्ण कलन विधि का समय इन चरणों के समय का योग है, O(n + k) है।[1][2]
क्योंकि यह लंबाई k + 1 और n के सरणियों का उपयोग करता है, एल्गोरिथ्म का कुल स्थान उपयोग भी O(n + k) है।[1]समस्या के उदाहरणों के लिए जिसमें अधिकतम कुंजी मान आइटमों की संख्या से काफी छोटा है, गिनती सॉर्ट अत्यधिक स्थान-कुशल हो सकता है, क्योंकि इसके इनपुट और आउटपुट एरे के अतिरिक्त यह एकमात्र स्टोरेज काउंट एरे है जो समष्टि O(k) का उपयोग करता है।[5]
संस्करण कलन विधि
यदि क्रमबद्ध किया जाने वाला प्रत्येक आइटम स्वयं एक पूर्णांक है, और कुंजी के रूप में भी उपयोग किया जाता है, तो गिनती क्रम के दूसरे और तीसरे लूप को जोड़ा जा सकता है; दूसरे लूप में, उस स्थिति की गणना करने के अतिरिक्त जहां कुंजी वाले आइटम हैं i आउटपुट में रखा जाना चाहिए, बस जोड़ें Count[i] संख्या की प्रतियां i आउटपुट के लिए है।
इस कलन विधि का उपयोग प्रतिलिपि कुंजियों को प्रतिस्थापित करके समाप्त करने के लिए भी किया जा सकता है Count एक बिट वेक्टर के साथ सरणी जो स्टोर करती है one एक कुंजी के लिए जो इनपुट में सम्मलित है और a zero उस कुंजी के लिए जो सम्मलित नहीं है। यदि अतिरिक्त आइटम स्वयं पूर्णांक कुंजियाँ हैं, तो दूसरे और तीसरे लूप दोनों को पूरी तरह से छोड़ा जा सकता है और बिट वेक्टर स्वयं आउटपुट के रूप में काम करेगा, मानों को गैर-ऑफ़सेट के रूप में प्रस्तुत करेगा।zero प्रविष्टियाँ, श्रेणी के न्यूनतम मान में जोड़ी गईं। इस प्रकार कुंजियाँ क्रमबद्ध हो जाती हैं और प्रतिलिपि को केवल बिट सरणी में रखकर इस संस्करण में समाप्त कर दिया जाता है।
उस डेटा के लिए जिसमें अधिकतम कुंजी आकार डेटा आइटमों की संख्या से काफी छोटा है, गिनती क्रम इनपुट को लगभग समान आकार के उपसरणी में विभाजित करके समानांतर कलन विधि हो सकती है, प्रत्येक उपसरणी के लिए एक अलग गिनती सरणी उत्पन्न करने के लिए समानांतर में प्रत्येक उपसरणी को संसाधित कर सकता है, और फिर गिनती सरणियों को विलय कर सकता है। जब समानांतर रेडिक्स सॉर्ट कलन विधि के हिस्से के रूप में उपयोग किया जाता है, तो विभाजित उपसरणी के आकार से मेल खाने के लिए कुंजी आकार (रेडिक्स प्रतिनिधित्व का आधार) चुना जाना चाहिए।[6] काउंटिंग सॉर्ट कलन विधि की सरलता और आसानी से समानांतर होने योग्य उपसर्ग सम प्रिमिटिव का उपयोग भी इसे अधिक सुक्ष्म समानांतर कलन विधि में प्रयोग करने योग्य बनाता है।[7] जैसा कि बताया गया है, सॉर्ट गिनती एक इन-प्लेस कलन विधि नहीं है; गिनती सरणी की उपेक्षा करते हुए भी, इसे अलग-अलग इनपुट और आउटपुट सरणी की आवश्यकता होती है। कलन विधि को संशोधित करना संभव है जिससे कि यह वस्तुओं को उसी सरणी के भीतर क्रमबद्ध क्रम में रखे जो इसे इनपुट के रूप में दिया गया था, केवल सहायक भंडारण के रूप में गिनती सरणी का उपयोग करके; चूंकि, गिनती क्रम का संशोधित इन-प्लेस संस्करण स्थिर नहीं है।[3]
इतिहास
चूंकि मूलांक प्रवरण का इतिहास बहुत पुराना है, काउंटिंग सॉर्ट, और रेडिक्स प्रवरण के लिए इसका अनुप्रयोग, दोनों का आविष्कार 1954 में हेरोल्ड एच. सीवार्ड द्वारा किया गया था।[1][4][8]
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "8.2 Counting Sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 168–170, ISBN 0-262-03293-7. See also the historical notes on page 181.
- ↑ 2.0 2.1 2.2 2.3 Edmonds, Jeff (2008), "5.2 Counting Sort (a Stable Sort)", How to Think about Algorithms, Cambridge University Press, pp. 72–75, ISBN 978-0-521-84931-9.
- ↑ 3.0 3.1 3.2 3.3 Sedgewick, Robert (2003), "6.10 Key-Indexed Counting", Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching (3rd ed.), Addison-Wesley, pp. 312–314.
- ↑ 4.0 4.1 Knuth, D. E. (1998), The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Addison-Wesley, ISBN 0-201-89685-0. Section 5.2, Sorting by counting, pp. 75–80, and historical notes, p. 170.
- ↑ Burris, David S.; Schember, Kurt (1980), "Sorting sequential files with limited auxiliary storage", Proceedings of the 18th annual Southeast Regional Conference, New York, NY, USA: ACM, pp. 23–31, doi:10.1145/503838.503855, ISBN 0897910141, S2CID 5670614.
- ↑ Zagha, Marco; Blelloch, Guy E. (1991), "Radix sort for vector multiprocessors", Proceedings of Supercomputing '91, November 18-22, 1991, Albuquerque, NM, USA, IEEE Computer Society / ACM, pp. 712–721, doi:10.1145/125826.126164, ISBN 0897914597.
- ↑ Reif, John H. (1985), "An optimal parallel algorithm for integer sorting", Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), pp. 496–504, doi:10.1109/SFCS.1985.9, ISBN 0-8186-0644-4, S2CID 5694693.
- ↑ Seward, H. H. (1954), "2.4.6 Internal Sorting by Floating Digital Sort", Information sorting in the application of electronic digital computers to business operations (PDF), Master's thesis, Report R-232, Massachusetts Institute of Technology, Digital Computer Laboratory, pp. 25–28.
बाहरी संबंध
- Counting Sort html5 visualization
- Demonstration applet from Cardiff University Archived 2013-06-02 at the Wayback Machine
- Kagel, Art S. (2 June 2006), "counting sort", in Black, Paul E. (ed.), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, retrieved 2011-04-21.
