गिनती क्रम
| Class | Sorting Algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | , where k is the range of the non-negative key values. |
| Worst-case space complexity |
कंप्यूटर विज्ञान में, काउंटिंग सॉर्ट, छोटे सकारात्मक पूर्णांक वाली कुंजियों के अनुसार वस्तुओं के संग्रह को सॉर्ट करने के लिए एक कलन विधि है; अर्थात्, यह एक पूर्णांक छँटाई एल्गोरिथ्म है। यह उन वस्तुओं की संख्या की गणना करके संचालित होता है जिनमें अलग-अलग कुंजी मान होते हैं, और आउटपुट अनुक्रम में प्रत्येक कुंजी मान की स्थिति निर्धारित करने के लिए उन गणनाओं पर उपसर्ग योग लागू करते हैं। इसका चलने का समय वस्तुओं की संख्या और अधिकतम कुंजी मान और न्यूनतम कुंजी मान के बीच अंतर में रैखिक है, इसलिए यह केवल उन स्थितियों में सीधे उपयोग के लिए उपयुक्त है जहां कुंजियों में भिन्नता वस्तुओं की संख्या से काफी अधिक नहीं है। इसे अक्सर आपको कामयाबी मिले में एक सबरूटीन के रूप में उपयोग किया जाता है, यह एक अन्य सॉर्टिंग एल्गोरिदम है, जो बड़ी कुंजियों को अधिक कुशलता से संभाल सकता है।[1][2][3] गिनती का प्रकार तुलनात्मक प्रकार नहीं है; यह किसी सरणी में अनुक्रमणिका के रूप में मुख्य मानों का उपयोग करता है Ω(n log n) तुलना छँटाई के लिए निचली सीमा लागू नहीं होगी।[1]बाल्टी प्रकार का उपयोग गिनती सॉर्ट के बदले में किया जा सकता है, और इसमें समान समय विश्लेषण शामिल होता है। हालाँकि, काउंटिंग सॉर्ट की तुलना में, बकेट सॉर्ट के लिए प्रत्येक बकेट के भीतर वस्तुओं के सेट को रखने के लिए लिंक की गई सूचियों, गतिशील सरणियों या पूर्व-आवंटित मेमोरी की एक बड़ी मात्रा की आवश्यकता होती है, जबकि काउंटिंग सॉर्ट प्रति बाल्टी एक एकल संख्या (आइटमों की गिनती) को संग्रहीत करता है। .[4]
इनपुट और आउटपुट धारणाएँ
सबसे सामान्य मामले में, काउंटिंग सॉर्ट के इनपुट में एक संग्रह (सार डेटा प्रकार) होता है n आइटम, जिनमें से प्रत्येक में एक गैर-नकारात्मक पूर्णांक कुंजी है जिसका अधिकतम मूल्य अधिकतम है k.[3]गिनती क्रम के कुछ विवरणों में, क्रमबद्ध किए जाने वाले इनपुट को पूर्णांकों का एक अनुक्रम मात्र माना जाता है,[1]लेकिन यह सरलीकरण गिनती के कई अनुप्रयोगों को समायोजित नहीं करता है। उदाहरण के लिए, जब रेडिक्स सॉर्ट में एक सबरूटीन के रूप में उपयोग किया जाता है, तो प्रत्येक कॉल के लिए काउंटिंग सॉर्ट की कुंजियाँ बड़ी आइटम कुंजियों के अलग-अलग अंक होती हैं; केवल आइटमों से अलग किए गए मुख्य अंकों की क्रमबद्ध सूची लौटाना पर्याप्त नहीं होगा।
रेडिक्स सॉर्ट जैसे अनुप्रयोगों में, अधिकतम कुंजी मान पर एक सीमा होती है k पहले से ज्ञात होगा, और इसे एल्गोरिथम के इनपुट का हिस्सा माना जा सकता है। हालाँकि, यदि का मान k पहले से ज्ञात नहीं है तो इसकी गणना, पहले चरण के रूप में, अधिकतम कुंजी मान निर्धारित करने के लिए डेटा पर एक अतिरिक्त लूप द्वारा की जा सकती है।
आउटपुट उनकी कुंजियों द्वारा क्रमित तत्वों की एक ऐरे डेटा संरचना है। रेडिक्स सॉर्टिंग के लिए इसके अनुप्रयोग के कारण, गिनती सॉर्ट एक स्थिर सॉर्ट होना चाहिए; अर्थात्, यदि दो तत्व एक ही कुंजी साझा करते हैं, तो आउटपुट सरणी में उनका सापेक्ष क्रम और इनपुट सरणी में उनका सापेक्ष क्रम मेल खाना चाहिए।[1][2]
छद्मकोड
छद्मकोड में, एल्गोरिथ्म को इस प्रकार व्यक्त किया जा सकता है:
फ़ंक्शन काउंटिंग सॉर्ट (इनपुट, k)
गिनती ← k + 1 शून्य की सरणी
आउटपुट ← इनपुट के समान लंबाई की सरणी
i = 0 से लंबाई (इनपुट) - 1 के लिए
j = कुंजी(इनपुट[i])
गिनती[जे] = गिनती[जे] + 1
i = 1 से k के लिए करें
गिनती[मैं] = गिनती[मैं] + गिनती[मैं - 1]
i के लिए = लंबाई(इनपुट) - 1 से 0 तक करें
j = कुंजी(इनपुट[i])
गिनती[जे] = गिनती[जे] - 1
आउटपुट[गिनती[जे = इनपुट[आई]
वापसी आउटपुट
यहाँ 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.
