गिनती क्रम: Difference between revisions

गिनती क्रम
Class	Sorting Algorithm
Data structure	Array
Worst-case performance	, where k is the range of the non-negative key values.
Worst-case space complexity

Revision as of 20:48, 2 August 2023

अभिकलित्र विज्ञान में, काउंटिंग सॉर्ट, छोटे सकारात्मक पूर्णांक वाली कुंजियों के अनुसार वस्तुओं के संग्रह को सॉर्ट करने के लिए एक कलन विधि है; अर्थात्, यह एक पूर्णांक प्रवरण कलन विधि है। यह उन वस्तुओं की संख्या की गणना करके संचालित होता है जिनमें अलग-अलग कुंजी मान होते हैं, और आउटपुट अनुक्रम में प्रत्येक कुंजी मान की स्थिति निर्धारित करने के लिए उन गणनाओं पर उपसर्ग योग लागू करते हैं। इसका चलने का समय वस्तुओं की संख्या और अधिकतम कुंजी मान और न्यूनतम कुंजी मान के बीच अंतर में रैखिक है, इसलिए यह केवल उन स्थितियों में सीधे उपयोग के लिए उपयुक्त है जहां कुंजियों में भिन्नता वस्तुओं की संख्या से काफी अधिक नहीं है। इसे अक्सर एक सबरूटीन के रूप में उपयोग किया जाता है, यह एक अन्य प्रवरण कलन विधि है, जो बड़ी कुंजियों को अधिक कुशलता से संभाल सकता है।^[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 यह निर्धारित करने के लिए, प्रत्येक कुंजी के लिए, वह स्थिति सीमा जहां उस कुंजी वाले आइटम रखे जाने चाहिए; यानी कुंजी के आइटम $i$ प्रारंभिक स्थिति में रखा जाना चाहिए count[ $i$ ]. अंत में, तीसरे लूप में, यह के आइटम्स पर लूप करता है 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.

[clrs-1] 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.

[edmonds-2] 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.

[sedgewick-3] 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.

[knuth-4] 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.

[5] 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.

[6] 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.

[7] 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.

[8] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 2: / Line 2: @@
 {{Infobox algorithm|class=[[Sorting Algorithm]]|data=[[Array data structure|Array]]|time=<math>O(n+k)</math>, where k is the range of the non-negative key values.|space=<math>O(n+k)</math>}}
-[[कंप्यूटर विज्ञान]] में, काउंटिंग सॉर्ट, छोटे सकारात्मक [[पूर्णांक]] वाली कुंजियों के अनुसार वस्तुओं के संग्रह को सॉर्ट करने के लिए एक [[कलन विधि]] है; अर्थात्, यह एक पूर्णांक [[छँटाई एल्गोरिथ्म]] है। यह उन वस्तुओं की संख्या की गणना करके संचालित होता है जिनमें अलग-अलग कुंजी मान होते हैं, और आउटपुट अनुक्रम में प्रत्येक कुंजी मान की स्थिति निर्धारित करने के लिए उन गणनाओं पर उपसर्ग योग लागू करते हैं। इसका चलने का समय वस्तुओं की संख्या और अधिकतम कुंजी मान और न्यूनतम कुंजी मान के बीच अंतर में रैखिक है, इसलिए यह केवल उन स्थितियों में सीधे उपयोग के लिए उपयुक्त है जहां कुंजियों में भिन्नता वस्तुओं की संख्या से काफी अधिक नहीं है। इसे अक्सर [[ आपको कामयाबी मिले ]] में एक सबरूटीन के रूप में उपयोग किया जाता है, यह एक अन्य सॉर्टिंग एल्गोरिदम है, जो बड़ी कुंजियों को अधिक कुशलता से संभाल सकता है।<ref name="clrs">{{citation
+[[Index.php?title=अभिकलित्र विज्ञान|अभिकलित्र विज्ञान]] में, '''काउंटिंग सॉर्ट''', छोटे सकारात्मक [[पूर्णांक]] वाली कुंजियों के अनुसार वस्तुओं के संग्रह को सॉर्ट करने के लिए एक [[कलन विधि]] है; अर्थात्, यह एक पूर्णांक [[Index.php?title=प्रवरण कलन विधि|प्रवरण कलन विधि]] है। यह उन वस्तुओं की संख्या की गणना करके संचालित होता है जिनमें अलग-अलग कुंजी मान होते हैं, और आउटपुट अनुक्रम में प्रत्येक कुंजी मान की स्थिति निर्धारित करने के लिए उन गणनाओं पर उपसर्ग योग लागू करते हैं। इसका चलने का समय वस्तुओं की संख्या और अधिकतम कुंजी मान और न्यूनतम कुंजी मान के बीच अंतर में रैखिक है, इसलिए यह केवल उन स्थितियों में सीधे उपयोग के लिए उपयुक्त है जहां कुंजियों में भिन्नता वस्तुओं की संख्या से काफी अधिक नहीं है। इसे अक्सर एक सबरूटीन के रूप में उपयोग किया जाता है, यह एक अन्य प्रवरण कलन विधि है, जो बड़ी कुंजियों को अधिक कुशलता से संभाल सकता है।<ref name="clrs">{{citation
   | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
   | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
@@ Line 14: / Line 14: @@
   | title = [[Introduction to Algorithms]]
   | year = 2001}}. See also the historical notes on page 181.</ref><ref name="edmonds">{{citation|first=Jeff|last=Edmonds|contribution=5.2 Counting Sort (a Stable Sort)|pages=72–75|title=How to Think about Algorithms|publisher=Cambridge University Press|year=2008|isbn=978-0-521-84931-9}}.</ref><ref name="sedgewick">{{citation|first=Robert|last=Sedgewick|author-link=Robert Sedgewick (computer scientist)|contribution=6.10 Key-Indexed Counting|title=Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching|edition=3rd|publisher=Addison-Wesley|year=2003|pages=312–314}}.</ref>
-गिनती का प्रकार तुलनात्मक प्रकार नहीं है; यह किसी सरणी में अनुक्रमणिका के रूप में मुख्य मानों का उपयोग करता है {{math|[[Big O notation#Family of Bachmann–Landau notations|Ω]](''n'' log ''n'')}} तुलना छँटाई के लिए निचली सीमा लागू नहीं होगी।<ref name="clrs"/>[[ बाल्टी प्रकार ]] का उपयोग गिनती सॉर्ट के बदले में किया जा सकता है, और इसमें समान समय विश्लेषण शामिल होता है। हालाँकि, काउंटिंग सॉर्ट की तुलना में, बकेट सॉर्ट के लिए प्रत्येक बकेट के भीतर वस्तुओं के सेट को रखने के लिए लिंक की गई सूचियों, गतिशील सरणियों या पूर्व-आवंटित मेमोरी की एक बड़ी मात्रा की आवश्यकता होती है, जबकि काउंटिंग सॉर्ट प्रति बाल्टी एक एकल संख्या (आइटमों की गिनती) को संग्रहीत करता है। .<ref name="knuth"/>
+गिनती का प्रकार तुलनात्मक प्रकार नहीं है; यह किसी सरणी में अनुक्रमणिका के रूप में मुख्य मानों का उपयोग करता है {{math|[[Big O notation#Family of Bachmann–Landau notations|Ω]](''n'' log ''n'')}} तुलना प्रवरण के लिए निचली सीमा लागू नहीं होगी।<ref name="clrs"/> [[Index.php?title=बकट सॉर्ट|बकट सॉर्ट]]  का उपयोग गिनती सॉर्ट के बदले में किया जा सकता है, और इसमें समान समय विश्लेषण शामिल होता है। हालाँकि, काउंटिंग सॉर्ट की तुलना में, बकेट सॉर्ट के लिए प्रत्येक बकेट के भीतर वस्तुओं के सेट को रखने के लिए लिंक की गई सूचियों, गतिशील सरणियों या पूर्व-आवंटित मेमोरी की एक बड़ी मात्रा की आवश्यकता होती है, जबकि काउंटिंग सॉर्ट प्रति बकट एक एकल संख्या (आइटमों की गिनती) को संग्रहीत करता है। .<ref name="knuth"/>
 ==इनपुट और आउटपुट धारणाएँ==
-सबसे सामान्य मामले में, काउंटिंग सॉर्ट के इनपुट में एक [[संग्रह (सार डेटा प्रकार)]] होता है {{mvar|n}} आइटम, जिनमें से प्रत्येक में एक गैर-नकारात्मक पूर्णांक कुंजी है जिसका अधिकतम मूल्य अधिकतम है {{mvar|k}}.<ref name="sedgewick"/>गिनती क्रम के कुछ विवरणों में, क्रमबद्ध किए जाने वाले इनपुट को पूर्णांकों का एक अनुक्रम मात्र माना जाता है,<ref name="clrs"/>लेकिन यह सरलीकरण गिनती के कई अनुप्रयोगों को समायोजित नहीं करता है। उदाहरण के लिए, जब रेडिक्स सॉर्ट में एक सबरूटीन के रूप में उपयोग किया जाता है, तो प्रत्येक कॉल के लिए काउंटिंग सॉर्ट की कुंजियाँ बड़ी आइटम कुंजियों के अलग-अलग अंक होती हैं; केवल आइटमों से अलग किए गए मुख्य अंकों की क्रमबद्ध सूची लौटाना पर्याप्त नहीं होगा।
+सबसे सामान्य मामले में, काउंटिंग सॉर्ट के इनपुट में n आइटमों का एक संग्रह होता है, जिनमें से प्रत्येक में एक गैर-नकारात्मक पूर्णांक कुंजी होती है जिसका अधिकतम मान अधिकतम k होता है। <ref name="sedgewick"/>गिनती क्रम के कुछ विवरणों में, क्रमबद्ध किए जाने वाले इनपुट को पूर्णांकों का एक अनुक्रम मात्र माना जाता है,<ref name="clrs"/>लेकिन यह सरलीकरण गिनती के कई अनुप्रयोगों को समायोजित नहीं करता है। उदाहरण के लिए, जब रेडिक्स सॉर्ट में एक सबरूटीन के रूप में उपयोग किया जाता है, तो प्रत्येक कॉल के लिए काउंटिंग सॉर्ट की कुंजियाँ बड़ी आइटम कुंजियों के अलग-अलग अंक होती हैं; केवल आइटमों से अलग किए गए मुख्य अंकों की क्रमबद्ध सूची लौटाना पर्याप्त नहीं होगा।
-रेडिक्स सॉर्ट जैसे अनुप्रयोगों में, अधिकतम कुंजी मान पर एक सीमा होती है {{mvar|k}} पहले से ज्ञात होगा, और इसे एल्गोरिथम के इनपुट का हिस्सा माना जा सकता है। हालाँकि, यदि का मान {{mvar|k}} पहले से ज्ञात नहीं है तो इसकी गणना, पहले चरण के रूप में, अधिकतम कुंजी मान निर्धारित करने के लिए डेटा पर एक अतिरिक्त लूप द्वारा की जा सकती है।
+रेडिक्स सॉर्ट जैसे अनुप्रयोगों में, अधिकतम कुंजी मान पर एक सीमा होती है {{mvar|k}} पहले से ज्ञात होगा, और इसे कलन विधि के इनपुट का हिस्सा माना जा सकता है। हालाँकि, यदि {{mvar|k}} का मान पहले से ज्ञात नहीं है तो इसकी गणना, पहले चरण के रूप में, अधिकतम कुंजी मान निर्धारित करने के लिए डेटा पर एक अतिरिक्त लूप द्वारा की जा सकती है।
-आउटपुट उनकी कुंजियों द्वारा क्रमित तत्वों की एक ऐरे डेटा संरचना है। रेडिक्स सॉर्टिंग के लिए इसके अनुप्रयोग के कारण, गिनती सॉर्ट एक स्थिर सॉर्ट होना चाहिए; अर्थात्, यदि दो तत्व एक ही कुंजी साझा करते हैं, तो आउटपुट सरणी में उनका सापेक्ष क्रम और इनपुट सरणी में उनका सापेक्ष क्रम मेल खाना चाहिए।<ref name="clrs"/><ref name="edmonds"/>
+आउटपुट उनकी कुंजियों द्वारा क्रमित तत्वों की एक ऐरे डेटा संरचना है। रेडिक्स प्रवरण के लिए इसके अनुप्रयोग के कारण, गिनती सॉर्ट एक स्थिर सॉर्ट होना चाहिए; अर्थात्, यदि दो तत्व एक ही कुंजी साझा करते हैं, तो आउटपुट सरणी में उनका सापेक्ष क्रम और इनपुट सरणी में उनका सापेक्ष क्रम मेल खाना चाहिए।<ref name="clrs"/><ref name="edmonds"/>
 ==छद्मकोड==
-छद्मकोड में, एल्गोरिथ्म को इस प्रकार व्यक्त किया जा सकता है:
+छद्मकोड में, कलन विधि को इस प्रकार व्यक्त किया जा सकता है:
-  फ़ंक्शन काउंटिंग सॉर्ट (इनपुट, ''k'')
+  '''function''' CountingSort(input, ''k'')
-      गिनती ← ''k'' + 1 शून्य की सरणी
+      count ← array of ''k'' + 1 zeros
-      आउटपुट ← इनपुट के समान लंबाई की सरणी
+      output ← array of same length as input
-      ''i'' = 0 से लंबाई (इनपुट) - 1 के लिए
+      '''for''' ''i'' = 0 '''to''' length(input) - 1 '''do'''
-          ''j'' = कुंजी(इनपुट[''i''])
+          ''j'' = key(input[''i''])
-          गिनती[''जे''] = गिनती[''जे''] + 1
+          count[''j''] = count[''j''] + 1
-      ''i'' = 1 से ''k'' के लिए करें
+      '''for''' ''i'' = 1 '''to''' ''k'' '''do'''
-          गिनती[''मैं''] = गिनती[''मैं''] + गिनती[''मैं'' - 1]
+          count[''i''] = count[''i''] + count[''i'' - 1]
-      ''i'' के लिए = लंबाई(इनपुट) - 1 से 0 तक करें
+      '''for''' ''i'' = length(input) - 1 '''down to''' 0 '''do'''
-          ''j'' = कुंजी(इनपुट[''i''])
+          ''j'' = key(input[''i''])
-          गिनती[''जे''] = गिनती[''जे''] - 1
+          count[''j''] = count[''j''] - 1
-          आउटपुट[गिनती[''जे'' = इनपुट[''आई'']
+          output[count[''j'']] = input[''i'']
-     वापसी आउटपुट
+     '''return''' output
 यहाँ <code>input</code> सॉर्ट किया जाने वाला इनपुट ऐरे है, <code>key</code> इनपुट सरणी में प्रत्येक आइटम की संख्यात्मक कुंजी लौटाता है, <code>count</code> एक सहायक सरणी है जिसका उपयोग पहले प्रत्येक कुंजी के साथ आइटमों की संख्या को संग्रहीत करने के लिए किया जाता है, और फिर (दूसरे लूप के बाद) उन स्थितियों को संग्रहीत करने के लिए किया जाता है जहां प्रत्येक कुंजी के साथ आइटम रखे जाने चाहिए,
 <code>k</code> गैर-नकारात्मक कुंजी मानों का अधिकतम मान है और <code>output</code> क्रमबद्ध आउटपुट सरणी है।
-संक्षेप में, एल्गोरिथ्म पहले लूप में आइटमों पर लूप करता है, प्रत्येक कुंजी के भीतर होने वाली संख्या के [[हिस्टोग्राम]] की गणना करता है <code>input</code> संग्रह। उसके बाद दूसरे लूप में, यह एक [[उपसर्ग योग]] गणना करता है <code>count</code> यह निर्धारित करने के लिए, प्रत्येक कुंजी के लिए, वह स्थिति सीमा जहां उस कुंजी वाले आइटम रखे जाने चाहिए; यानी कुंजी के आइटम <math>i</math> प्रारंभिक स्थिति में रखा जाना चाहिए <code>count[<math>i</math>]</code>. अंत में, तीसरे लूप में, यह के आइटम्स पर लूप करता है <code>input</code> फिर से, लेकिन उल्टे क्रम में, प्रत्येक आइटम को उसकी क्रमबद्ध स्थिति में ले जाना <code>output</code> सरणी.<ref name="clrs"/><ref name="edmonds"/><ref name="sedgewick"/>
+संक्षेप में, कलन विधि पहले लूप में आइटमों पर लूप करता है, प्रत्येक कुंजी के भीतर होने वाली संख्या के [[हिस्टोग्राम]] की गणना करता है <code>input</code> संग्रह, उसके बाद दूसरे लूप में, यह एक [[उपसर्ग योग]] गणना करता है <code>count</code> यह निर्धारित करने के लिए, प्रत्येक कुंजी के लिए, वह स्थिति सीमा जहां उस कुंजी वाले आइटम रखे जाने चाहिए; यानी कुंजी के आइटम <math>i</math> प्रारंभिक स्थिति में रखा जाना चाहिए <code>count[<math>i</math>]</code>. अंत में, तीसरे लूप में, यह के आइटम्स पर लूप करता है <code>input</code> फिर से, लेकिन उल्टे क्रम में, प्रत्येक आइटम को उसकी क्रमबद्ध स्थिति में ले जाना <code>output</code> सरणी है।<ref name="clrs"/><ref name="edmonds"/><ref name="sedgewick"/>
 समान कुंजियों वाली वस्तुओं का सापेक्ष क्रम यहां संरक्षित है; यानी, यह एक :श्रेणी:स्थिर प्रकार है।
 ==जटिलता विश्लेषण==
-क्योंकि एल्गोरिदम केवल सरल फॉर लूप का उपयोग करता है, रिकर्सन या सबरूटीन कॉल के बिना, इसका विश्लेषण करना सीधा है। गिनती सरणी का आरंभीकरण, और दूसरा लूप के लिए जो गिनती सरणी पर एक उपसर्ग योग करता है, प्रत्येक अधिकतम पर पुनरावृत्त होता है {{math|''k'' + 1}} बार और इसलिए ले लो {{math|''O''(''k'')}} समय। लूप के लिए अन्य दो, और आउटपुट ऐरे का आरंभीकरण, प्रत्येक लेता है {{math|''O''(''n'')}} समय। इसलिए, संपूर्ण एल्गोरिदम का समय इन चरणों के समय का योग है, {{math|''O''(''n'' + ''k'')}}.<ref name="clrs"/><ref name="edmonds"/>
+क्योंकि कलन विधि केवल सरल फॉर लूप का उपयोग करता है, रिकर्सन या सबरूटीन कॉल के बिना, इसका विश्लेषण करना सीधा है। गिनती सरणी का आरंभीकरण, और दूसरा लूप के लिए जो गिनती सरणी पर एक उपसर्ग योग करता है, प्रत्येक अधिकतम k + 1 बार पुनरावृत्त होता है और इसलिए O(k) समय लेता है। लूप के लिए अन्य दो, और आउटपुट ऐरे का आरंभीकरण, प्रत्येक O(n) समय लेता है। इसलिए, संपूर्ण कलन विधि का समय इन चरणों के समय का योग है, {{math|''O''(''n'' + ''k'')}} है।<ref name="clrs"/><ref name="edmonds"/>
-क्योंकि यह लंबाई की सारणियों का उपयोग करता है {{math|''k'' + 1}} और {{mvar|n}}, एल्गोरिदम का कुल स्थान उपयोग भी है {{math|''O''(''n'' + ''k'')}}.<ref name="clrs"/>समस्या के उदाहरणों के लिए जिसमें अधिकतम कुंजी मान आइटमों की संख्या से काफी कम है, गिनती सॉर्ट अत्यधिक स्थान-कुशल हो सकता है, क्योंकि यह अपने इनपुट और आउटपुट सरणी के अलावा एकमात्र भंडारण का उपयोग करता है जो गिनती सरणी है जो अंतरिक्ष का उपयोग करता है {{math|''O''(''k'')}}.<ref>{{citation
+क्योंकि यह लंबाई k + 1 और n के सरणियों का उपयोग करता है, एल्गोरिथ्म का कुल स्थान उपयोग भी O(n + k) है।<ref name="clrs"/>समस्या के उदाहरणों के लिए जिसमें अधिकतम कुंजी मान आइटमों की संख्या से काफी छोटा है, गिनती सॉर्ट अत्यधिक स्थान-कुशल हो सकता है, क्योंकि इसके इनपुट और आउटपुट एरे के अलावा यह एकमात्र स्टोरेज काउंट एरे है जो समष्टि {{math|''O''(''k'')}} का उपयोग करता है।<ref>{{citation
   | last1 = Burris | first1 = David S.
   | last2 = Schember | first2 = Kurt
@@ Line 71: / Line 71: @@
-==संस्करण एल्गोरिदम==
+==संस्करण कलन विधि==
-यदि क्रमबद्ध किया जाने वाला प्रत्येक आइटम स्वयं एक पूर्णांक है, और कुंजी के रूप में भी उपयोग किया जाता है, तो गिनती क्रम के दूसरे और तीसरे लूप को जोड़ा जा सकता है; दूसरे लूप में, उस स्थिति की गणना करने के बजाय जहां कुंजी वाले आइटम हैं <code>i</code> आउटपुट में रखा जाना चाहिए, बस जोड़ें <code>Count[i]</code> संख्या की प्रतियां <code>i</code> आउटपुट के लिए.
+यदि क्रमबद्ध किया जाने वाला प्रत्येक आइटम स्वयं एक पूर्णांक है, और कुंजी के रूप में भी उपयोग किया जाता है, तो गिनती क्रम के दूसरे और तीसरे लूप को जोड़ा जा सकता है; दूसरे लूप में, उस स्थिति की गणना करने के बजाय जहां कुंजी वाले आइटम हैं <code>i</code> आउटपुट में रखा जाना चाहिए, बस जोड़ें <code>Count[i]</code> संख्या की प्रतियां <code>i</code> आउटपुट के लिए है।
-इस एल्गोरिदम का उपयोग डुप्लिकेट कुंजियों को प्रतिस्थापित करके समाप्त करने के लिए भी किया जा सकता है <code>Count</code> एक [[बिट वेक्टर]] के साथ सरणी जो स्टोर करती है <code>one</code> एक कुंजी के लिए जो इनपुट में मौजूद है और a <code>zero</code> उस कुंजी के लिए जो मौजूद नहीं है। यदि अतिरिक्त आइटम स्वयं पूर्णांक कुंजियाँ हैं, तो दूसरे और तीसरे लूप दोनों को पूरी तरह से छोड़ा जा सकता है और बिट वेक्टर स्वयं आउटपुट के रूप में काम करेगा, मानों को गैर-ऑफ़सेट के रूप में प्रस्तुत करेगा।<code>zero</code> प्रविष्टियाँ, श्रेणी के न्यूनतम मान में जोड़ी गईं। इस प्रकार कुंजियाँ क्रमबद्ध हो जाती हैं और डुप्लिकेट को केवल बिट सरणी में रखकर इस संस्करण में समाप्त कर दिया जाता है।
+इस कलन विधि का उपयोग प्रतिलिपि कुंजियों को प्रतिस्थापित करके समाप्त करने के लिए भी किया जा सकता है <code>Count</code> एक [[बिट वेक्टर]] के साथ सरणी जो स्टोर करती है <code>one</code> एक कुंजी के लिए जो इनपुट में मौजूद है और a <code>zero</code> उस कुंजी के लिए जो मौजूद नहीं है। यदि अतिरिक्त आइटम स्वयं पूर्णांक कुंजियाँ हैं, तो दूसरे और तीसरे लूप दोनों को पूरी तरह से छोड़ा जा सकता है और बिट वेक्टर स्वयं आउटपुट के रूप में काम करेगा, मानों को गैर-ऑफ़सेट के रूप में प्रस्तुत करेगा।<code>zero</code> प्रविष्टियाँ, श्रेणी के न्यूनतम मान में जोड़ी गईं। इस प्रकार कुंजियाँ क्रमबद्ध हो जाती हैं और प्रतिलिपि को केवल बिट सरणी में रखकर इस संस्करण में समाप्त कर दिया जाता है।
-उस डेटा के लिए जिसमें अधिकतम कुंजी आकार डेटा आइटमों की संख्या से काफी छोटा है, गिनती क्रम इनपुट को लगभग समान आकार के उपसरणी में विभाजित करके [[समानांतर एल्गोरिदम]] हो सकता है, प्रत्येक उपसरणी के लिए एक अलग गिनती सरणी उत्पन्न करने के लिए समानांतर में प्रत्येक उपसरणी को संसाधित कर सकता है, और फिर गिनती सरणियों को विलय कर सकता है। जब समानांतर रेडिक्स सॉर्ट एल्गोरिदम के हिस्से के रूप में उपयोग किया जाता है, तो विभाजित उपसरणी के आकार से मेल खाने के लिए कुंजी आकार (रेडिक्स प्रतिनिधित्व का आधार) चुना जाना चाहिए।<ref>{{citation
+उस डेटा के लिए जिसमें अधिकतम कुंजी आकार डेटा आइटमों की संख्या से काफी छोटा है, गिनती क्रम इनपुट को लगभग समान आकार के उपसरणी में विभाजित करके [[समानांतर एल्गोरिदम|समानांतर कलन विधि]] हो सकती है, प्रत्येक उपसरणी के लिए एक अलग गिनती सरणी उत्पन्न करने के लिए समानांतर में प्रत्येक उपसरणी को संसाधित कर सकता है, और फिर गिनती सरणियों को विलय कर सकता है। जब समानांतर रेडिक्स सॉर्ट कलन विधि के हिस्से के रूप में उपयोग किया जाता है, तो विभाजित उपसरणी के आकार से मेल खाने के लिए कुंजी आकार (रेडिक्स प्रतिनिधित्व का आधार) चुना जाना चाहिए।<ref>{{citation
   | last1 = Zagha | first1 = Marco
   | last2 = Blelloch | first2 = Guy E. | author2-link = Guy Blelloch
@@ Line 86: / Line 86: @@
   | year = 1991| isbn = 0897914597
   | url = https://www.cs.cmu.edu/~scandal/papers/cray-sort-supercomputing91.ps.gz| doi-access = free
-  }}.</ref> काउंटिंग सॉर्ट एल्गोरिदम की सरलता और आसानी से समानांतर होने योग्य उपसर्ग सम प्रिमिटिव का उपयोग भी इसे अधिक सुक्ष्म समानांतर एल्गोरिदम में प्रयोग करने योग्य बनाता है।<ref>{{citation
+  }}.</ref> काउंटिंग सॉर्ट कलन विधि की सरलता और आसानी से समानांतर होने योग्य उपसर्ग सम प्रिमिटिव का उपयोग भी इसे अधिक सुक्ष्म समानांतर कलन विधि में प्रयोग करने योग्य बनाता है।<ref>{{citation
   | last = Reif | first = John H. | author-link = John Reif
   | contribution = An optimal parallel algorithm for integer sorting
@@ Line 93: / Line 93: @@
   | title = [[Symposium on Foundations of Computer Science|Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985)]]
   | year = 1985| isbn = 0-8186-0644-4 | s2cid = 5694693 }}.</ref>
-जैसा कि बताया गया है, सॉर्ट गिनती एक [[इन-प्लेस एल्गोरिदम]] नहीं है; गिनती सरणी की उपेक्षा करते हुए भी, इसे अलग-अलग इनपुट और आउटपुट सरणी की आवश्यकता होती है। एल्गोरिदम को संशोधित करना संभव है ताकि यह वस्तुओं को उसी सरणी के भीतर क्रमबद्ध क्रम में रखे जो इसे इनपुट के रूप में दिया गया था, केवल सहायक भंडारण के रूप में गिनती सरणी का उपयोग करके; हालाँकि, गिनती क्रम का संशोधित इन-प्लेस संस्करण स्थिर नहीं है।<ref name="sedgewick"/>
+जैसा कि बताया गया है, सॉर्ट गिनती एक [[इन-प्लेस एल्गोरिदम|इन-प्लेस कलन विधि]] नहीं है; गिनती सरणी की उपेक्षा करते हुए भी, इसे अलग-अलग इनपुट और आउटपुट सरणी की आवश्यकता होती है। कलन विधि को संशोधित करना संभव है ताकि यह वस्तुओं को उसी सरणी के भीतर क्रमबद्ध क्रम में रखे जो इसे इनपुट के रूप में दिया गया था, केवल सहायक भंडारण के रूप में गिनती सरणी का उपयोग करके; हालाँकि, गिनती क्रम का संशोधित इन-प्लेस संस्करण स्थिर नहीं है।<ref name="sedgewick"/>
 ==इतिहास==
-हालाँकि मूलांक छँटाई का इतिहास बहुत पुराना है,
+हालाँकि मूलांक प्रवरण का इतिहास बहुत पुराना है,
-काउंटिंग सॉर्ट, और रेडिक्स सॉर्टिंग के लिए इसका अनुप्रयोग, दोनों का आविष्कार 1954 में हेरोल्ड एच. सीवार्ड द्वारा किया गया था।<ref name="clrs"/><ref name="knuth">{{citation|first=D. E.|last=Knuth|author-link=Donald Knuth|title=[[The Art of Computer Programming]], Volume 3: Sorting and Searching|edition=2nd|publisher=Addison-Wesley|year=1998|isbn=0-201-89685-0}}. Section 5.2, Sorting by counting, pp.&nbsp;75–80, and historical notes, p.&nbsp;170.</ref><ref>{{citation|first=H. H.|last=Seward|title=Information sorting in the application of electronic digital computers to business operations|series=Master's thesis, Report R-232|year=1954|publisher=[[Massachusetts Institute of Technology]], Digital Computer Laboratory|url=http://bitsavers.org/pdf/mit/whirlwind/R-series/R-232_Information_Sorting_in_the_Application_of_Electronic_Digital_Computers_to_Business_Operations_May54.pdf|contribution=2.4.6 Internal Sorting by Floating Digital Sort|pages=25–28}}.</ref>
+काउंटिंग सॉर्ट, और रेडिक्स प्रवरण के लिए इसका अनुप्रयोग, दोनों का आविष्कार 1954 में हेरोल्ड एच. सीवार्ड द्वारा किया गया था।<ref name="clrs"/><ref name="knuth">{{citation|first=D. E.|last=Knuth|author-link=Donald Knuth|title=[[The Art of Computer Programming]], Volume 3: Sorting and Searching|edition=2nd|publisher=Addison-Wesley|year=1998|isbn=0-201-89685-0}}. Section 5.2, Sorting by counting, pp.&nbsp;75–80, and historical notes, p.&nbsp;170.</ref><ref>{{citation|first=H. H.|last=Seward|title=Information sorting in the application of electronic digital computers to business operations|series=Master's thesis, Report R-232|year=1954|publisher=[[Massachusetts Institute of Technology]], Digital Computer Laboratory|url=http://bitsavers.org/pdf/mit/whirlwind/R-series/R-232_Information_Sorting_in_the_Application_of_Electronic_Digital_Computers_to_Business_Operations_May54.pdf|contribution=2.4.6 Internal Sorting by Floating Digital Sort|pages=25–28}}.</ref>

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

गिनती क्रम: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:48, 2 August 2023

Contents

इनपुट और आउटपुट धारणाएँ

छद्मकोड

जटिलता विश्लेषण

संस्करण कलन विधि

इतिहास

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

गिनती क्रम: Difference between revisions

Revision as of 20:48, 2 August 2023

इनपुट और आउटपुट धारणाएँ

छद्मकोड

जटिलता विश्लेषण

संस्करण कलन विधि

इतिहास

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories