बोगोसोर्ट: Difference between revisions

बोगोसोर्ट
Class	Sorting
Data structure	Array
Worst-case performance	Unbounded (randomized version), (deterministic version)
Best-case performance
Average performance
Worst-case space complexity

Latest revision as of 12:58, 12 September 2023

कंप्यूटर विज्ञान में, बोगोसॉर्ट^[1]^[2] (क्रमपरिवर्तन सॉर्ट, मंद सॉर्ट^[3], स्लोसॉर्ट या बोज़ोसॉर्ट के रूप में भी जाना जाता है) उत्पन्न और परीक्षण प्रतिमान पर आधारित एक श्रेणीकरण कलन विधि है। फलन क्रमिक रूप से अपने निविष्ट के क्रम परिवर्तन उत्पन्न करता है जब तक कि उसे कोई क्रमपरिवर्तन जो क्रमबद्ध हो नहीं मिल जाता है। इसे श्रेणीकरण के लिए उपयोगी नहीं माना जाता है, लेकिन इसे अधिक कुशल कलन विधि के साथ तुलना करने, शैक्षिक उद्देश्यों के लिए उपयोग किया जा सकता है।

इस कलन विधि के दो संस्करण उपस्थित हैं जिसमे एक नियतात्मक संस्करण जो सभी क्रमपरिवर्तनों की गणना करता है जब तक कि यह एक क्रमबद्ध क्रम में न आ जाए,^[2]^[4] और एक यादृच्छिक कलन विधि संस्करण जो यादृच्छिक रूप से अपने निविष्ट को क्रमपरिवर्तित करता है। बाद वाले संस्करण के व्यवसाय के लिए एक सादृश्य यह है कि डेक को हवा में फेंककर, यादृच्छिक रूप से पत्तों को उठाकर, और डेक के छंटने तक प्रक्रिया को पुनरावृत्ति हुए ताश के पत्तों को क्रमबद्ध किया जाए। इसका नाम बोगस और सॉर्ट शब्दों से मिलकर बना है।^[5]

कलन विधि का विवरण

छद्मकोड में यादृच्छिक कलन विधि का विवरण निम्नलिखित है:

while not sorted(deck):

shuffle(deck)

यहां उपरोक्त छद्मकोड को पायथन 3 में पुनः लिखा गया है:

from random import shuffle

def is_sorted(data) -> bool:
    """Determine whether the data is sorted."""
    return all(a <= b for a, b in zip(data, data[1:]))

def bogosort(data) -> list:
    """Shuffle data until sorted."""
    while not is_sorted(data):
        shuffle(data)

    return data

यह कोड मानता है डेटा एक सरल, परिवर्तनशील, सरणी-जैसी डेटा संरचना है - जैसे कि पायथन में अंतर्निहित सूची—जिनके तत्वों की तुलना बिना किसी समस्या के की जा सकती है।

कार्यकारी समय और समाप्ति

बोगोसॉर्ट का प्रायोगिक रनटाइम

यदि क्रमबद्ध किए जाने वाले सभी तत्व अलग-अलग हैं, तो यादृच्छिक बोगोसॉर्ट द्वारा औसत सन्दर्भ में की गई तुलनाओं की अपेक्षित संख्या स्पर्शोन्मुख रूप से $(e - 1) n!$ , के बराबर है और औसत सन्दर्भ में विनिमय की अपेक्षित संख्या $(n - 1) n!$ के बराबर होती है .^[1] विनिमय की अपेक्षित संख्या तुलनाओं की अपेक्षित संख्या की तुलना में शीघ्रता से बढ़ती है, क्योंकि यदि तत्व क्रम में नहीं हैं, तो यह सामान्यतः केवल कुछ तुलनाओं के बाद ही अन्वेषण किया जाएगा, चाहे कितने भी तत्व हों लेकिन संग्रह में परिवर्तन का कार्य उसके आकार के समानुपाती होता है। सबसे निकृष्ट स्थिति में, तुलना और विनिमय दोनों की संख्या असीमित है, इसी कारण से कि एक उछाला गया सिक्का लगातार कितनी भी बार चित आ सकता है।

सबसे अच्छी स्थिति तब होती है जब दी गई सूची पहले से ही क्रमबद्ध हो जिससे की इस सन्दर्भ में तुलनाओं की अपेक्षित संख्या है $n - 1$ है, और कोई भी विनिमय नहीं किया जाता है।^[1]

निश्चित आकार के किसी भी संग्रह के लिए, कलन विधि का अपेक्षित कार्यकारी समय उसी कारण से सीमित है जो अनंत मंकी प्रमेय रखता है, सही क्रमपरिवर्तन प्राप्त करने की कुछ संभावना है, इसलिए असीमित संख्या में प्रयासों को देखते हुए यह लगभग निश्चित रूप से अंततः होगा चुना जाए।

संबंधित कलन विधि

गोरोसोर्ट: गूगल कोड जैम 2011 में एक श्रेणीकरण कलन विधि प्रस्तुत किया गया।^[6] जब तक सूची क्रम में नहीं होती, सभी तत्वों का एक उपसमूह यादृच्छिक रूप से क्रमबद्ध होता है। यदि इस उपसमुच्चय को प्रत्येक बार निष्पादित करते समय इष्टतम रूप से चुना जाता है, तो इस संचालन को करने की कुल संख्या का अपेक्षित मूल्य गलत रखे गए तत्वों की संख्या के बराबर है।
बोजोबोगोसॉर्ट: एक कलन विधि जो सूची की प्रारम्भ की छोटी और छोटी प्रतियों के साथ पुनरावर्ती रूप से निमंत्रण करता है यह देखने के लिए कि क्या वे क्रमबद्ध हैं। आधारभूत स्थिति एक एकल तत्व है, जिसे प्रायः क्रमबद्ध किया जाता है। अन्य स्थितिके लिए, यह सूची में पिछले तत्वों के अंतिम तत्व की तुलना अधिकतम तत्व से करता है। यदि अंतिम तत्व बड़ा या बराबर है, तो यह जांचता है कि प्रतिलिपि का क्रम पिछले संस्करण से मेल खाता है या नहीं, और यदि हां तो वापस आ जाता है। अन्यथा, यह सूची की वर्तमान प्रतिलिपि में परिवर्तन करता है और इसकी पुनरावर्ती जांच को पुनरारंभ करता है।^[7]
बोगोसोर्ट: यादृच्छिक संख्याओं पर आधारित एक और श्रेणीकरण कलन विधि है। यदि सूची क्रम में नहीं है, तो यह यादृच्छिक रूप से दो वस्तु चुनता है और उन्हें विनिमय करता है, फिर यह देखने के लिए जांच करता है कि सूची क्रमबद्ध है या नहीं है। बोज़ोसॉर्ट का कार्यकारी समय विश्लेषण अधिक कठिन है, लेकिन कुछ अनुमान एच. ग्रुबर के "विकृत रूप से भयानक" यादृच्छिक श्रेणीकरण कलन विधि के विश्लेषण में पाए जाते हैं।^[1] $O (n!)$ अपेक्षित औसत मामला पाया गया है।
वर्स्टसोर्ट: एक निराशाजनक^{[lower-alpha 1]} श्रेणीकरण कलन विधि जिसे सीमित समय में पूरा करने की आश्वासन दी जाती है; यद्यपि, इसकी विन्यास के आधार पर इसकी दक्षता मनमाने ढंग से खराब हो सकती है। $वर्स्टसोर्ट$ कलन विधि वर्स्टसोर्ट श्रेणीकरण कलन विधि बैडसॉर्ट परआधारित है। बैडसॉर्ट कलन विधि दो मापदंडों को स्वीकार करता है: $L$ , जो क्रमबद्ध की जाने वाली सूची है, और $k$ , जो एक प्रत्यावर्तन गहराई है। प्रत्यावर्तन स्तर $k = 0$ पर $बैडसॉर्ट$ अपने निविष्ट को सॉर्ट करने और सॉर्ट की गई सूची को वापस करने के लिए केवल बबलसॉर्ट जैसे सामान्य श्रेणीकरण कलन विधि का उपयोग करता है। कहने का तात्पर्य यह है कि, $badsort(L, 0) = bubblesort(L)$ . इसलिए, यदि k = 0 है तो बैडसॉर्ट की समय जटिलता O(n2) है। यद्यपि, किसी भी k > 0 के लिए, बैडसॉर्ट(L, k) पहले P उत्पन्न करता है, जो L के सभी क्रमपरिवर्तनों की सूची है।फिर, बैडसॉर्ट $badsort(P, k - 1)$ , की गणना करता है, और क्रमबद्ध किए गए $P$ का पहला तत्व लौटाता है। वर्स्टसॉर्ट को वास्तव में निराशाजनक बनाने के लिए, $k$ को एक गणना योग्य बढ़ते फ़ंक्शन के मान को सौंपा जा सकता है जैसे कि $f\colon \mathbb {N} \to \mathbb {N}$ (उदा $f (n) = A (n, n)$ ,जहां $A$ एकरमैन का कार्य है)। इसलिए, किसी सूची को मनमाने ढंग से बुरी तरह क्रमबद्ध करने के लिए, कोई निष्पादित करेगा $worstsort(L, f) = badsort(L, f (length(L)))$ , जहां $L$ $लंबाई(L)$ में तत्वों की संख्या है। परिणामी कलन विधि में जटिलता है ${\textstyle \Omega \left(\left(n!^{(f(n))}\right)^{2}\right)}$ , कहाँ $n!^{(m)}=(\dotso ((n!)!)!\dotso )!$ = का भाज्य $n$ पुनरावृत्त $m$ बार. पर्याप्त तेजी से बढ़ने वाले कार्य $f$ को चुनकर इस कलन विधि को जितना चाहें उतना अक्षम बनाया जा सकता है।^[8]
स्लोसॉर्ट: एक अलग विनोदी श्रेणीकरण कलन विधि जो बड़े स्तर पर जटिलता प्राप्त करने के लिए एक पथभ्रष्ट विभाजन और जीत रणनीति को नियोजित करता है।
परिमाण बोगोसॉर्ट: बोगोसॉर्ट पर आधारित एक काल्पनिक श्रेणीकरण कलन विधि, कंप्यूटर वैज्ञानिकों के बीच परिहास के रूप में बनाया गया। कलन विधि एन्ट्रापी के परिमाण स्रोत का उपयोग करके अपने निविष्ट का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करता है, जाँच करता है कि क्या सूची क्रमबद्ध है, और, यदि यह नहीं है, तो ब्रह्मांड को नष्ट कर देता है। यह मानते हुए कि कई-जगत की व्याख्या मान्य है, इस कलन विधि के उपयोग के परिणामस्वरूप कम से कम एक जीवित ब्रह्मांड होगा जहां निविष्ट को $O (n)$ समय सफलतापूर्वक क्रमबद्ध किया गया था।^[9]
कौतुक सॉर्ट: एक श्रेणीकरण कलन विधि जो जांच करता है कि कोई कौतुक होने तक सरणी क्रमबद्ध की गई है या नहीं की गई है । यह क्रमबद्ध होने तक सरणी की लगातार जाँच करता रहता है, सरणी का क्रम कभी नहीं बदलता है।^[10] क्योंकि क्रम कभी नहीं बदला जाता है, कलन विधि में $O (\infty)$ एक काल्पनिक समय जटिलता होती है , लेकिन यह अभी भी चमत्कार या एकल-घटना उथल-पुथल जैसी घटनाओं को सुलझा सकता है। इस कलन विधि के कार्यान्वयन में विशेष सावधानी रखनी चाहिए क्योंकि अनुकूलन करने वाले संकलक इसे थोड़ी देर (सही) पाश में बदल सकते हैं। यद्यपि, सबसे अच्छी स्थिति $O (n)$ है, जो क्रमबद्ध सूची पर होता है।

यह भी देखें

लास वेगास कलन विधि
कठपुतली प्रकार

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Gruber, H.; Holzer, M.; Ruepp, O., "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17.
↑ ^2.0 ^2.1 Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF), SIGPLAN Notices, pp. 192–203, doi:10.1145/1086365.1086390, S2CID 1435535, archived from the original (PDF) on 26 March 2012, retrieved 22 June 2011
↑ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
↑ Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science, vol. 225, Springer-Verlag, pp. 624–634, doi:10.1007/3-540-16492-8_111.
↑ "बोगोसॉर्ट". xlinux.nist.gov. Retrieved 11 November 2020.
↑ Google Code Jam 2011, Qualification Rounds, Problem D
↑ Bogobogosort
↑ Lerma, Miguel A. (2014). "How inefficient can a sort algorithm be?". arXiv:1406.1077 [cs.DS].
↑ The Other Tree (23 October 2009). "क्वांटम बोगोसॉर्ट" (PDF). mathNEWS. 111 (3): 13. Retrieved 20 March 2022.
↑ "मिरेकल सॉर्ट - द कंप्यूटर साइंस हैंडबुक". www.thecshandbook.com. Retrieved 9 September 2022.

बाहरी संबंध

BogoSort on WikiWikiWeb
Inefficient sort algorithms
Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.
Bogosort and jmmcg::bogosort^{[permanent dead link]}: Simple, yet perverse, C++ implementations of the bogosort algorithm.
Bogosort NPM package: bogosort implementation for Node.js ecosystem.
Max Sherman Bogo-sort is Sort of Slow, June 2013

[pessimal-8] The opposite of "optimal"

[Fun07-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Gruber, H.; Holzer, M.; Ruepp, O., "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17.

[KSFS-2] 2.0 ^2.1 Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF), SIGPLAN Notices, pp. 192–203, doi:10.1145/1086365.1086390, S2CID 1435535, archived from the original (PDF) on 26 March 2012, retrieved 22 June 2011

[3] E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.

[Naish86-4] Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science, vol. 225, Springer-Verlag, pp. 624–634, doi:10.1007/3-540-16492-8_111.

[5] "बोगोसॉर्ट". xlinux.nist.gov. Retrieved 11 November 2020.

[6] Google Code Jam 2011, Qualification Rounds, Problem D

[7] Bogobogosort

[9] Lerma, Miguel A. (2014). "How inefficient can a sort algorithm be?". arXiv:1406.1077 [cs.DS].

[10] The Other Tree (23 October 2009). "क्वांटम बोगोसॉर्ट" (PDF). mathNEWS. 111 (3): 13. Retrieved 20 March 2022.

[11] "मिरेकल सॉर्ट - द कंप्यूटर साइंस हैंडबुक". www.thecshandbook.com. Retrieved 9 September 2022.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[8]

[9]

[10]

@@ Line 11: / Line 11: @@
 }}
-[[कंप्यूटर विज्ञान]] में, बोगोसॉर्ट<ref name="Fun07"/><ref name="KSFS">{{citation
+[[कंप्यूटर विज्ञान]] में, '''बोगोसॉर्ट'''<ref name="Fun07"/><ref name="KSFS">{{citation
   | last1 = Kiselyov
   | first1 = Oleg
@@ Line 32: / Line 32: @@
   | archive-date = 26 March 2012
   | url-status = dead
-  }}</ref> (क्रमपरिवर्तन सॉर्ट, स्टुपिड सॉर्ट के रूप में भी जाना जाता है,<ref>E. S. Raymond. "bogo-sort". ''The New Hacker’s Dictionary''. MIT Press, 1996.</ref> स्लोसॉर्ट या बोज़ोसॉर्ट) [[उत्पन्न करें और परीक्षण करें]] प्रतिमान पर आधारित एक [[छँटाई एल्गोरिथ्म]] है। फ़ंक्शन क्रमिक रूप से अपने इनपुट के क्रम[[परिवर्तन]] उत्पन्न करता है जब तक कि उसे कोई क्रमपरिवर्तन नहीं मिल जाता जो क्रमबद्ध है। इसे सॉर्टिंग के लिए उपयोगी नहीं माना जाता है, लेकिन इसे अधिक कुशल एल्गोरिदम के साथ तुलना करने के लिए शैक्षिक उद्देश्यों के लिए उपयोग किया जा सकता है।
+  }}</ref> (क्रमपरिवर्तन सॉर्ट, मंद सॉर्ट<ref>E. S. Raymond. "bogo-sort". ''The New Hacker’s Dictionary''. MIT Press, 1996.</ref>, स्लोसॉर्ट या बोज़ोसॉर्ट के रूप में भी जाना जाता है) [[उत्पन्न करें और परीक्षण करें|उत्पन्न और परीक्षण]] प्रतिमान पर आधारित एक [[छँटाई एल्गोरिथ्म|श्रेणीकरण कलन विधि]] है। फलन क्रमिक रूप से अपने निविष्ट के क्रम परिवर्तन उत्पन्न करता है जब तक कि उसे कोई क्रमपरिवर्तन जो क्रमबद्ध हो नहीं मिल जाता  है। इसे श्रेणीकरण के लिए उपयोगी नहीं माना जाता है, लेकिन इसे अधिक कुशल कलन विधि के साथ तुलना करने, शैक्षिक उद्देश्यों के लिए उपयोग किया जा सकता है।
-इस एल्गोरिथ्म के दो संस्करण मौजूद हैं: एक नियतात्मक संस्करण जो सभी क्रमपरिवर्तनों की गणना करता है जब तक कि यह एक क्रमबद्ध क्रम में न आ जाए,<ref name="KSFS"/><ref name="Naish86">{{citation |last=Naish |first=Lee |title=Proceedings of the Third International Conference on Logic Programming |volume=225 |pages=624–634 |year=1986 |series=[[Lecture Notes in Computer Science]] |contribution=Negation and quantifiers in NU-Prolog |publisher=Springer-Verlag |doi=10.1007/3-540-16492-8_111}}.</ref> और एक [[यादृच्छिक एल्गोरिदम]] संस्करण जो अपने इनपुट को यादृच्छिक रूप से क्रमपरिवर्तित करता है। बाद वाले संस्करण के कामकाज के लिए एक सादृश्य यह है कि डेक को हवा में फेंककर, यादृच्छिक रूप से कार्डों को उठाकर, और डेक के छंटने तक प्रक्रिया को दोहराते हुए ताश के पत्तों को क्रमबद्ध किया जाए। इसका नाम बोगस और सॉर्ट शब्दों से मिलकर बना है।<ref>{{Cite web|title=बोगोसॉर्ट|url=https://xlinux.nist.gov/dads/HTML/बोगोसॉर्ट.html|access-date=2020-11-11|website=xlinux.nist.gov}}</ref>
+इस कलन विधि के दो संस्करण उपस्थित हैं जिसमे एक नियतात्मक संस्करण जो सभी क्रमपरिवर्तनों की गणना करता है जब तक कि यह एक क्रमबद्ध क्रम में न आ जाए,<ref name="KSFS"/><ref name="Naish86">{{citation |last=Naish |first=Lee |title=Proceedings of the Third International Conference on Logic Programming |volume=225 |pages=624–634 |year=1986 |series=[[Lecture Notes in Computer Science]] |contribution=Negation and quantifiers in NU-Prolog |publisher=Springer-Verlag |doi=10.1007/3-540-16492-8_111}}.</ref> और एक [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] संस्करण जो यादृच्छिक रूप से अपने निविष्ट को क्रमपरिवर्तित करता है। बाद वाले संस्करण के व्यवसाय के लिए एक सादृश्य यह है कि डेक को हवा में फेंककर, यादृच्छिक रूप से पत्तों को उठाकर, और डेक के छंटने तक प्रक्रिया को पुनरावृत्ति हुए ताश के पत्तों को क्रमबद्ध किया जाए। इसका नाम बोगस और सॉर्ट शब्दों से मिलकर बना है।<ref>{{Cite web|title=बोगोसॉर्ट|url=https://xlinux.nist.gov/dads/HTML/बोगोसॉर्ट.html|access-date=2020-11-11|website=xlinux.nist.gov}}</ref>
+==कलन विधि का विवरण==
+छद्मकोड में यादृच्छिक कलन विधि का विवरण निम्नलिखित है:
+ '''while not''' sorted(deck):
-==एल्गोरिदम का विवरण==
+ shuffle(deck)
-स्यूडोकोड में यादृच्छिक एल्गोरिदम का विवरण निम्नलिखित है:
-  जबकि क्रमबद्ध नहीं (डेक):
+यहां उपरोक्त [[छद्मकोड]] को [[पायथन (प्रोग्रामिंग भाषा)|पायथन 3]] में पुनः लिखा गया है:
-      फेरबदल(डेक)
+ from random import shuffle
+ def is_sorted(data) -> bool:
+     """Determine whether the data is sorted."""
+     return all(a <= b for a, b in zip(data, data[1:]))
+ def bogosort(data) -> list:
+      """Shuffle data until sorted."""
+     while not is_sorted(data):
+         shuffle(data)
-यहां उपरोक्त [[छद्मकोड]] को [[पायथन (प्रोग्रामिंग भाषा)]] में फिर से लिखा गया है:
+     return data
+यह कोड मानता है {{code|डेटा}} एक सरल, परिवर्तनशील, सरणी-जैसी डेटा संरचना है - जैसे कि पायथन में अंतर्निहित {{code|सूची}}—जिनके तत्वों की तुलना बिना किसी समस्या के की जा सकती है।
-<सिंटैक्सहाइलाइट लैंग = पायथन3 >
+==कार्यकारी समय और समाप्ति==
-यादृच्छिक आयात फेरबदल से
+[[File:ExperimentalBogosort.png|thumb|बोगोसॉर्ट का प्रायोगिक रनटाइम]]यदि क्रमबद्ध किए जाने वाले सभी तत्व अलग-अलग हैं, तो यादृच्छिक बोगोसॉर्ट द्वारा औसत सन्दर्भ में की गई तुलनाओं की अपेक्षित संख्या स्पर्शोन्मुख रूप से {{math|(''e'' − 1)''n''!}}, के बराबर है और औसत सन्दर्भ में विनिमय की अपेक्षित संख्या {{math|(''n'' − 1)''n''!}} के बराबर होती है .<ref name="Fun07">{{citation
-def is_sorted(data) -> बूल:
-       निर्धारित करें कि डेटा सॉर्ट किया गया है या नहीं.
-    सभी लौटाएँ(a <= b for a, b in zip(data, data[1:]))
-डीईएफ़ बोगोसॉर्ट(डेटा) -> सूची:
-       क्रमबद्ध होने तक डेटा को शफ़ल करें।
-    जबकि is_sorted(डेटा) नहीं है:
-        फेरबदल(डेटा)
-    डेटा वापस करें
-</सिंटैक्सहाइलाइट>
-यह कोड ऐसा मानता है {{code|data}} एक सरल, परिवर्तनशील, सरणी-जैसी डेटा संरचना है - जैसे कि पायथन में निर्मित {{code|list}}—जिनके तत्वों की तुलना बिना किसी समस्या के की जा सकती है।
-==चलने का समय और समाप्ति==
-[[File:ExperimentalBogosort.png|thumb|बोगोसॉर्ट का प्रायोगिक रनटाइम]]यदि क्रमबद्ध किए जाने वाले सभी तत्व अलग-अलग हैं, तो यादृच्छिक बोगोसॉर्ट द्वारा औसत मामले में की गई तुलनाओं की अपेक्षित संख्या एसिम्प्टोटिक विश्लेषण है {{math|(''e'' − 1)''n''!}}, और औसत मामले में स्वैप की अपेक्षित संख्या बराबर होती है {{math|(''n'' − 1)''n''!}}.<ref name="Fun07">{{citation
   | last1 = Gruber | first1 = H.
   | last2 = Holzer | first2 = M.
@@ Line 73: / Line 69: @@
   | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007
   | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf
-  | volume = 4475}}.</ref> स्वैप की अपेक्षित संख्या तुलनाओं की अपेक्षित संख्या की तुलना में तेजी से बढ़ती है, क्योंकि यदि तत्व क्रम में नहीं हैं, तो यह आमतौर पर केवल कुछ तुलनाओं के बाद ही खोजा जाएगा, चाहे कितने भी तत्व हों; लेकिन संग्रह में फेरबदल का कार्य उसके आकार के समानुपाती होता है। सबसे खराब स्थिति में, तुलना और स्वैप दोनों की संख्या असीमित है, इसी कारण से कि एक उछाला गया सिक्का लगातार कितनी भी बार चित आ सकता है।
+  | volume = 4475}}.</ref> विनिमय की अपेक्षित संख्या तुलनाओं की अपेक्षित संख्या की तुलना में शीघ्रता से बढ़ती है, क्योंकि यदि तत्व क्रम में नहीं हैं, तो यह सामान्यतः केवल कुछ तुलनाओं के बाद ही अन्वेषण किया जाएगा, चाहे कितने भी तत्व हों लेकिन संग्रह में परिवर्तन का कार्य उसके आकार के समानुपाती होता है। सबसे निकृष्ट स्थिति में, तुलना और  विनिमय दोनों की संख्या असीमित है, इसी कारण से कि एक उछाला गया सिक्का लगातार कितनी भी बार चित आ सकता है।
-सबसे अच्छी स्थिति तब होती है जब दी गई सूची पहले से ही क्रमबद्ध हो; इस मामले में तुलनाओं की अपेक्षित संख्या है {{math|''n'' − 1}}, और कोई भी स्वैप नहीं किया जाता है।<ref name="Fun07"/>
+सबसे अच्छी स्थिति तब होती है जब दी गई सूची पहले से ही क्रमबद्ध हो जिससे की इस सन्दर्भ में तुलनाओं की अपेक्षित संख्या है {{math|''n'' − 1}} है, और कोई भी  विनिमय नहीं किया जाता है।<ref name="Fun07"/>
-निश्चित आकार के किसी भी संग्रह के लिए, एल्गोरिदम का अपेक्षित चलने का समय उसी कारण से सीमित है जो [[अनंत बंदर प्रमेय]] रखता है: सही क्रमपरिवर्तन प्राप्त करने की कुछ संभावना है, इसलिए असीमित संख्या में प्रयासों को देखते हुए यह [[लगभग निश्चित रूप से]] अंततः होगा चुना जाए.
+निश्चित आकार के किसी भी संग्रह के लिए, कलन विधि का अपेक्षित कार्यकारी समय उसी कारण से सीमित है जो [[अनंत बंदर प्रमेय|अनंत मंकी प्रमेय]] रखता है, सही क्रमपरिवर्तन प्राप्त करने की कुछ संभावना है, इसलिए असीमित संख्या में प्रयासों को देखते हुए यह [[लगभग निश्चित रूप से]] अंततः होगा चुना जाए।
-==संबंधित एल्गोरिदम==
+==संबंधित कलन विधि==
-;{{visible anchor|Gorosort}}: 2011 Google कोड जैम में एक सॉर्टिंग एल्गोरिदम पेश किया गया।<ref>[https://code.google.com/codejam/contest/dashboard?c=975485#s=p3 Google Code Jam 2011, Qualification Rounds, Problem D]</ref> जब तक सूची क्रम में नहीं होती, सभी तत्वों का एक उपसमूह यादृच्छिक रूप से क्रमबद्ध होता है। यदि इस उपसमुच्चय को हर बार निष्पादित करते समय इष्टतम रूप से चुना जाता है, तो इस ऑपरेशन को करने की कुल संख्या का [[अपेक्षित मूल्य]] गलत रखे गए तत्वों की संख्या के बराबर है।
+;{{visible anchor|गोरोसोर्ट}}: गूगल कोड जैम 2011 में एक श्रेणीकरण कलन विधि प्रस्तुत किया गया।<ref>[https://code.google.com/codejam/contest/dashboard?c=975485#s=p3 Google Code Jam 2011, Qualification Rounds, Problem D]</ref> जब तक सूची क्रम में नहीं होती, सभी तत्वों का एक उपसमूह यादृच्छिक रूप से क्रमबद्ध होता है। यदि इस उपसमुच्चय को प्रत्येक बार निष्पादित करते समय इष्टतम रूप से चुना जाता है, तो इस संचालन को करने की कुल संख्या का [[अपेक्षित मूल्य]] गलत रखे गए तत्वों की संख्या के बराबर है।
-;{{visible anchor|Bogobogosort}}: एक एल्गोरिदम जो सूची की शुरुआत की छोटी और छोटी प्रतियों के साथ पुनरावर्ती रूप से कॉल करता है यह देखने के लिए कि क्या वे क्रमबद्ध हैं। बेस केस एक एकल तत्व है, जिसे हमेशा क्रमबद्ध किया जाता है। अन्य मामलों के लिए, यह सूची में पिछले तत्वों के अंतिम तत्व की तुलना अधिकतम तत्व से करता है। यदि अंतिम तत्व बड़ा या बराबर है, तो यह जांचता है कि प्रतिलिपि का क्रम पिछले संस्करण से मेल खाता है या नहीं, और यदि हां तो वापस आ जाता है। अन्यथा, यह सूची की वर्तमान प्रतिलिपि में फेरबदल करता है और इसकी पुनरावर्ती जांच को पुनरारंभ करता है।<ref>[http://www.dangermouse.net/esoteric/bogobogosort.html Bogobogosort]</ref>
+;{{visible anchor|बोजोबोगोसॉर्ट}}: एक कलन विधि जो सूची की प्रारम्भ की छोटी और छोटी प्रतियों के साथ पुनरावर्ती रूप से निमंत्रण करता है यह देखने के लिए कि क्या वे क्रमबद्ध हैं। आधारभूत स्थिति एक एकल तत्व है, जिसे प्रायः क्रमबद्ध किया जाता है। अन्य स्थितिके लिए, यह सूची में पिछले तत्वों के अंतिम तत्व की तुलना अधिकतम तत्व से करता है। यदि अंतिम तत्व बड़ा या बराबर है, तो यह जांचता है कि प्रतिलिपि का क्रम पिछले संस्करण से मेल खाता है या नहीं, और यदि हां तो वापस आ जाता है। अन्यथा, यह सूची की वर्तमान प्रतिलिपि में परिवर्तन करता है और इसकी पुनरावर्ती जांच को पुनरारंभ करता है।<ref>[http://www.dangermouse.net/esoteric/bogobogosort.html Bogobogosort]</ref>
 <!-- Bogobogosort needs to be implemented recursively, as in the iterative version it is too easy to optimize out the second bogo. -->
-;{{visible anchor|Bozosort}}: यादृच्छिक संख्याओं पर आधारित एक और सॉर्टिंग एल्गोरिदम। यदि सूची क्रम में नहीं है, तो यह यादृच्छिक रूप से दो आइटम चुनता है और उन्हें स्वैप करता है, फिर यह देखने के लिए जांच करता है कि सूची क्रमबद्ध है या नहीं। बोज़ोसॉर्ट का रनिंग टाइम विश्लेषण अधिक कठिन है, लेकिन कुछ अनुमान एच. ग्रुबर के विकृत रूप से भयानक यादृच्छिक सॉर्टिंग एल्गोरिदम के विश्लेषण में पाए जाते हैं।<ref name="Fun07"/> {{math|''O''(''n''!)}}अपेक्षित औसत मामला पाया गया है।
+;{{visible anchor|बोगोसोर्ट}}: यादृच्छिक संख्याओं पर आधारित एक और श्रेणीकरण कलन विधि है। यदि सूची क्रम में नहीं है, तो यह यादृच्छिक रूप से दो वस्तु चुनता है और उन्हें  विनिमय करता है, फिर यह देखने के लिए जांच करता है कि सूची क्रमबद्ध है या नहीं है। बोज़ोसॉर्ट का कार्यकारी समय विश्लेषण अधिक कठिन है, लेकिन कुछ अनुमान एच. ग्रुबर के "विकृत रूप से भयानक" यादृच्छिक श्रेणीकरण कलन विधि के विश्लेषण में पाए जाते हैं।<ref name="Fun07"/> {{math|''O''(''n''!)}}अपेक्षित औसत मामला पाया गया है।
 <!--It also faces the same pseudo-random problems as bogosort—it may never terminate in a real-world implementation.-->
-;{{visible anchor|Worstsort}}: एक निराशावादी{{efn|name=pessimal|The opposite of "optimal"}} सॉर्टिंग एल्गोरिदम जो सीमित समय में पूरा होने की गारंटी देता है; हालाँकि, इसकी कॉन्फ़िगरेशन के आधार पर इसकी दक्षता मनमाने ढंग से खराब हो सकती है। वह {{math|worstsort}} एल्गोरिदम खराब सॉर्टिंग एल्गोरिदम पर आधारित है, {{math|badsort}}. बैडसॉर्ट एल्गोरिदम दो पैरामीटर स्वीकार करता है: {{mvar|L}}, जो क्रमबद्ध की जाने वाली सूची है, और {{mvar|k}}, जो एक प्रत्यावर्तन गहराई है। प्रत्यावर्तन स्तर पर {{math|1=''k'' = 0}}, {{math|badsort}} अपने इनपुट को सॉर्ट करने और सॉर्ट की गई सूची को वापस करने के लिए केवल एक सामान्य सॉर्टिंग एल्गोरिदम, जैसे [[ बुलबुले की तरह ]], का उपयोग करता है। यानी, {{math|1=badsort(''L'', 0) = bubblesort(''L'')}}. इसलिए, बैडसॉर्ट की समय जटिलता है {{math|''O''(''n''<sup>2</sup>)}} अगर {{math|1=''k'' = 0}}. हालाँकि, किसी के लिए भी {{math|''k'' > 0}}, {{math|badsort(''L'', ''k'')}} पहले उत्पन्न करता है {{mvar|P}}, के सभी क्रमपरिवर्तन की सूची {{mvar|L}}. तब, {{math|badsort}} गणना करता है {{math|badsort(''P'', ''k'' − 1)}}, और क्रमबद्ध का पहला तत्व लौटाता है {{mvar|P}}. बनाने के लिए {{math|worstsort}} वास्तव में निराशावादी, {{mvar|k}} को एक गणना योग्य बढ़ते फ़ंक्शन के मान को सौंपा जा सकता है जैसे कि <math>f\colon\N \to \N</math> (उदा {{math|1=''f''(''n'') = ''A''(''n'', ''n'')}}, कहाँ {{mvar|A}} एकरमैन का कार्य है)। इसलिए, किसी सूची को मनमाने ढंग से बुरी तरह क्रमबद्ध करने के लिए, कोई निष्पादित करेगा {{math|1=worstsort(''L'', ''f'') = badsort(''L'', ''f''(length(''L'')))}}, कहाँ {{math|length(''L'')}} में तत्वों की संख्या है {{mvar|L}}. परिणामी एल्गोरिदम में जटिलता है <math display="inline">\Omega\left(\left(n!^{(f(n))}\right)^2\right)</math>, कहाँ <math>n!^{(m)} = (\dotso((n!)!)!\dotso)!</math> = का भाज्य {{mvar|n}} पुनरावृत्त {{mvar|m}} बार. पर्याप्त तेजी से बढ़ने वाले फ़ंक्शन को चुनकर इस एल्गोरिदम को जितना चाहें उतना अक्षम बनाया जा सकता है {{mvar|f}}.<ref>{{Cite arXiv |eprint = 1406.1077|last1 = Lerma|first1 = Miguel A.|title = How inefficient can a sort algorithm be?|class = cs.DS|year = 2014}}</ref>
+;{{visible anchor|वर्स्टसोर्ट}}: एक निराशाजनक{{efn|name=pessimal|The opposite of "optimal"}} श्रेणीकरण कलन विधि जिसे सीमित समय में पूरा करने की आश्वासन दी जाती है; यद्यपि, इसकी विन्यास के आधार पर इसकी दक्षता मनमाने ढंग से खराब हो सकती है।  {{math|वर्स्टसोर्ट}} कलन विधि वर्स्टसोर्ट श्रेणीकरण कलन विधि '''बैडसॉर्ट''' परआधारित है। बैडसॉर्ट कलन विधि दो मापदंडों को स्वीकार करता है: {{mvar|L}}, जो क्रमबद्ध की जाने वाली सूची है, और {{mvar|k}}, जो एक प्रत्यावर्तन गहराई है। प्रत्यावर्तन स्तर {{math|1=''k'' = 0}} पर {{math|बैडसॉर्ट}} अपने  निविष्ट को सॉर्ट करने और सॉर्ट की गई सूची को वापस करने के लिए केवल बबलसॉर्ट जैसे सामान्य श्रेणीकरण कलन विधि  का उपयोग करता है। कहने का तात्पर्य यह है कि, {{math|1=badsort(''L'', 0) = bubblesort(''L'')}}. इसलिए, यदि k = 0 है तो  बैडसॉर्ट की समय जटिलता O(n2) है। यद्यपि, किसी भी k > 0 के लिए,  बैडसॉर्ट(L, k) पहले P उत्पन्न करता है, जो L के सभी क्रमपरिवर्तनों की सूची है।फिर, बैडसॉर्ट {{math|badsort(''P'', ''k'' − 1)}}, की गणना करता है, और क्रमबद्ध किए गए {{mvar|P}} का पहला तत्व लौटाता है। वर्स्टसॉर्ट को वास्तव में निराशाजनक बनाने के लिए, {{mvar|k}} को एक गणना योग्य बढ़ते फ़ंक्शन के मान को सौंपा जा सकता है जैसे कि <math>f\colon\N \to \N</math> (उदा {{math|1=''f''(''n'') = ''A''(''n'', ''n'')}},जहां {{mvar|A}} एकरमैन का कार्य है)। इसलिए, किसी सूची को मनमाने ढंग से बुरी तरह क्रमबद्ध करने के लिए, कोई निष्पादित करेगा {{math|1=worstsort(''L'', ''f'') = badsort(''L'', ''f''(length(''L'')))}}, जहां {{mvar|L}} {{math|लंबाई(''L'')}} में तत्वों की संख्या है। परिणामी कलन विधि में जटिलता है <math display="inline">\Omega\left(\left(n!^{(f(n))}\right)^2\right)</math>, कहाँ <math>n!^{(m)} = (\dotso((n!)!)!\dotso)!</math> = का भाज्य {{mvar|n}} पुनरावृत्त {{mvar|m}} बार. पर्याप्त तेजी से बढ़ने वाले कार्य {{mvar|f}} को चुनकर इस कलन विधि को जितना चाहें उतना अक्षम बनाया जा सकता है।<ref>{{Cite arXiv |eprint = 1406.1077|last1 = Lerma|first1 = Miguel A.|title = How inefficient can a sort algorithm be?|class = cs.DS|year = 2014}}</ref>
-;[[स्लोसॉर्ट]]: एक अलग विनोदी सॉर्टिंग एल्गोरिदम जो बड़े पैमाने पर जटिलता प्राप्त करने के लिए एक गुमराह विभाजन और जीत रणनीति को नियोजित करता है।
+;[[स्लोसॉर्ट]]: एक अलग विनोदी श्रेणीकरण कलन विधि जो बड़े स्तर पर जटिलता प्राप्त करने के लिए एक पथभ्रष्ट विभाजन और जीत रणनीति को नियोजित करता है।
-;{{visible anchor|Quantum bogosort}}: बोगोसॉर्ट पर आधारित एक काल्पनिक सॉर्टिंग एल्गोरिदम, कंप्यूटर वैज्ञानिकों के बीच मजाक के रूप में बनाया गया। एल्गोरिथ्म एन्ट्रापी के क्वांटम स्रोत का उपयोग करके अपने इनपुट का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करता है, जाँच करता है कि क्या सूची क्रमबद्ध है, और, यदि यह नहीं है, तो ब्रह्मांड को नष्ट कर देता है। यह मानते हुए कि कई-दुनिया की व्याख्या मान्य है, इस एल्गोरिदम के उपयोग के परिणामस्वरूप कम से कम एक जीवित ब्रह्मांड होगा जहां इनपुट को सफलतापूर्वक सॉर्ट किया गया था {{math|''O''(''n'')}} समय।<ref>{{cite journal |author=The Other Tree |date=23 October 2009 |title=क्वांटम बोगोसॉर्ट|url=https://mathnews.uwaterloo.ca/wp-content/uploads/2014/08/v111i3-compressed.pdf#page=13 |journal=mathNEWS |volume=111 |issue=3 |page=13 |access-date=20 March 2022}}</ref>
+;{{visible anchor|परिमाण बोगोसॉर्ट}}: बोगोसॉर्ट पर आधारित एक काल्पनिक श्रेणीकरण कलन विधि, कंप्यूटर वैज्ञानिकों के बीच परिहास के रूप में बनाया गया। कलन विधि एन्ट्रापी के परिमाण स्रोत का उपयोग करके अपने  निविष्ट का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करता है, जाँच करता है कि क्या सूची क्रमबद्ध है, और, यदि यह नहीं है, तो ब्रह्मांड को नष्ट कर देता है। यह मानते हुए कि कई-जगत की व्याख्या मान्य है, इस कलन विधि के उपयोग के परिणामस्वरूप कम से कम एक जीवित ब्रह्मांड होगा जहां निविष्ट को {{math|''O''(''n'')}} समय सफलतापूर्वक क्रमबद्ध किया गया था।<ref>{{cite journal |author=The Other Tree |date=23 October 2009 |title=क्वांटम बोगोसॉर्ट|url=https://mathnews.uwaterloo.ca/wp-content/uploads/2014/08/v111i3-compressed.pdf#page=13 |journal=mathNEWS |volume=111 |issue=3 |page=13 |access-date=20 March 2022}}</ref>
-;{{visible anchor|Miracle sort}}: एक सॉर्टिंग एल्गोरिदम जो जांच करता है कि कोई [[चमत्कार]] होने तक सरणी सॉर्ट की गई है या नहीं। यह क्रमबद्ध होने तक सरणी की लगातार जाँच करता रहता है, सरणी का क्रम कभी नहीं बदलता।<ref>{{Cite web |title=मिरेकल सॉर्ट - द कंप्यूटर साइंस हैंडबुक|url=https://www.thecshandbook.com/Miracle_Sort |access-date=2022-09-09 |website=www.thecshandbook.com}}</ref> क्योंकि क्रम कभी नहीं बदला जाता है, एल्गोरिथ्म में एक काल्पनिक समय जटिलता होती है {{math|''O''(''∞'')}}, लेकिन यह अभी भी चमत्कार या एकल-घटना उथल-पुथल जैसी घटनाओं को सुलझा सकता है। इस एल्गोरिदम के कार्यान्वयन में विशेष सावधानी बरतनी चाहिए क्योंकि अनुकूलन करने वाले कंपाइलर इसे थोड़ी देर (सही) लूप में बदल सकते हैं। हालाँकि, सबसे अच्छा मामला है {{math|''O''(''n'')}}, जो क्रमबद्ध सूची पर होता है।
+;{{visible anchor|कौतुक सॉर्ट}}: एक श्रेणीकरण कलन विधि जो जांच करता है कि कोई [[चमत्कार|कौतुक]] होने तक सरणी क्रमबद्ध की गई है या नहीं की गई है । यह क्रमबद्ध होने तक सरणी की लगातार जाँच करता रहता है, सरणी का क्रम कभी नहीं बदलता है।<ref>{{Cite web |title=मिरेकल सॉर्ट - द कंप्यूटर साइंस हैंडबुक|url=https://www.thecshandbook.com/Miracle_Sort |access-date=2022-09-09 |website=www.thecshandbook.com}}</ref> क्योंकि क्रम कभी नहीं बदला जाता है, कलन विधि में {{math|''O''(''∞'')}} एक काल्पनिक समय जटिलता होती है , लेकिन यह अभी भी चमत्कार या एकल-घटना उथल-पुथल जैसी घटनाओं को सुलझा सकता है। इस कलन विधि के कार्यान्वयन में विशेष सावधानी रखनी चाहिए क्योंकि अनुकूलन करने वाले संकलक इसे थोड़ी देर (सही) पाश में बदल सकते हैं। यद्यपि, सबसे अच्छी स्थिति {{math|''O''(''n'')}} है, जो क्रमबद्ध सूची पर होता है।
 ==यह भी देखें==
-* [[लास वेगास एल्गोरिथ्म]]
+* [[लास वेगास एल्गोरिथ्म|लास वेगास कलन विधि]]
 * कठपुतली प्रकार
 ==टिप्पणियाँ==
 {{notelist}}
 ==संदर्भ==
@@ Line 110: / Line 105: @@
 * [https://github.com/spugachev/random-sort Bogosort NPM package]: bogosort implementation for Node.js ecosystem.
 * Max Sherman [https://sites.math.washington.edu/~morrow/336_13/papers/max.pdf Bogo-sort is Sort of Slow], June 2013
-{{sorting}}
-[[Category: छँटाई एल्गोरिदम]] [[Category: तुलना प्रकार]] [[Category: कंप्यूटर हास्य]] [[Category: उदाहरण के लिए पायथन (प्रोग्रामिंग भाषा) कोड वाले लेख]]
-[[Category: Machine Translated Page]]
+[[Category:All articles with dead external links]]
+[[Category:Articles with dead external links from July 2020]]
+[[Category:Articles with permanently dead external links]]
+[[Category:Collapse templates]]
 [[Category:Created On 27/06/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Use dmy dates from December 2021]]
+[[Category:Wikipedia metatemplates]]
+[[Category:उदाहरण के लिए पायथन (प्रोग्रामिंग भाषा) कोड वाले लेख]]
+[[Category:कंप्यूटर हास्य]]
+[[Category:छँटाई एल्गोरिदम]]
+[[Category:तुलना प्रकार]]

Anonymous

Search

बोगोसोर्ट: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:58, 12 September 2023

Contents

कलन विधि का विवरण

कार्यकारी समय और समाप्ति

संबंधित कलन विधि

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बोगोसोर्ट: Difference between revisions

Latest revision as of 12:58, 12 September 2023

कलन विधि का विवरण

कार्यकारी समय और समाप्ति

संबंधित कलन विधि

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories