बोगोसोर्ट

बोगोसोर्ट

Class	Sorting
Data structure	Array
Worst-case performance	Unbounded (randomized version), $O(n\times n!)$ (deterministic version)
Best-case performance	$\Omega (n)$
Average performance	$\Theta (n\times n!)$
Worst-case space complexity	$O(1)$

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

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

एल्गोरिदम का विवरण

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

जबकि क्रमबद्ध नहीं (डेक):
    फेरबदल(डेक)

यहां उपरोक्त छद्मकोड को पायथन (प्रोग्रामिंग भाषा) में फिर से लिखा गया है:

<सिंटैक्सहाइलाइट लैंग = पायथन3 > यादृच्छिक आयात फेरबदल से

def is_sorted(data) -> बूल:

      निर्धारित करें कि डेटा सॉर्ट किया गया है या नहीं.
   सभी लौटाएँ(a <= b for a, b in zip(data, data[1:]))

डीईएफ़ बोगोसॉर्ट(डेटा) -> सूची:

      क्रमबद्ध होने तक डेटा को शफ़ल करें।
   जबकि is_sorted(डेटा) नहीं है:
       फेरबदल(डेटा)
   डेटा वापस करें

</सिंटैक्सहाइलाइट>

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

चलने का समय और समाप्ति

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

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

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

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

संबंधित एल्गोरिदम

Gorosort

2011 Google कोड जैम में एक सॉर्टिंग एल्गोरिदम पेश किया गया। जब तक सूची क्रम में नहीं होती, सभी तत्वों का एक उपसमूह यादृच्छिक रूप से क्रमबद्ध होता है। यदि इस उपसमुच्चय को हर बार निष्पादित करते समय इष्टतम रूप से चुना जाता है, तो इस ऑपरेशन को करने की कुल संख्या का अपेक्षित मूल्य गलत रखे गए तत्वों की संख्या के बराबर है।

Bogobogosort

एक एल्गोरिदम जो सूची की शुरुआत की छोटी और छोटी प्रतियों के साथ पुनरावर्ती रूप से कॉल करता है यह देखने के लिए कि क्या वे क्रमबद्ध हैं। बेस केस एक एकल तत्व है, जिसे हमेशा क्रमबद्ध किया जाता है। अन्य मामलों के लिए, यह सूची में पिछले तत्वों के अंतिम तत्व की तुलना अधिकतम तत्व से करता है। यदि अंतिम तत्व बड़ा या बराबर है, तो यह जांचता है कि प्रतिलिपि का क्रम पिछले संस्करण से मेल खाता है या नहीं, और यदि हां तो वापस आ जाता है। अन्यथा, यह सूची की वर्तमान प्रतिलिपि में फेरबदल करता है और इसकी पुनरावर्ती जांच को पुनरारंभ करता है।

Bozosort

यादृच्छिक संख्याओं पर आधारित एक और सॉर्टिंग एल्गोरिदम। यदि सूची क्रम में नहीं है, तो यह यादृच्छिक रूप से दो आइटम चुनता है और उन्हें स्वैप करता है, फिर यह देखने के लिए जांच करता है कि सूची क्रमबद्ध है या नहीं। बोज़ोसॉर्ट का रनिंग टाइम विश्लेषण अधिक कठिन है, लेकिन कुछ अनुमान एच. ग्रुबर के विकृत रूप से भयानक यादृच्छिक सॉर्टिंग एल्गोरिदम के विश्लेषण में पाए जाते हैं। O(n!)अपेक्षित औसत मामला पाया गया है।

Worstsort

एक निराशावादी सॉर्टिंग एल्गोरिदम जो सीमित समय में पूरा होने की गारंटी देता है; हालाँकि, इसकी कॉन्फ़िगरेशन के आधार पर इसकी दक्षता मनमाने ढंग से खराब हो सकती है। वह worstsort एल्गोरिदम खराब सॉर्टिंग एल्गोरिदम पर आधारित है, badsort. बैडसॉर्ट एल्गोरिदम दो पैरामीटर स्वीकार करता है: L, जो क्रमबद्ध की जाने वाली सूची है, और k, जो एक प्रत्यावर्तन गहराई है। प्रत्यावर्तन स्तर पर k = 0, badsort अपने इनपुट को सॉर्ट करने और सॉर्ट की गई सूची को वापस करने के लिए केवल एक सामान्य सॉर्टिंग एल्गोरिदम, जैसे बुलबुले की तरह , का उपयोग करता है। यानी, badsort(L, 0) = bubblesort(L). इसलिए, बैडसॉर्ट की समय जटिलता है O(n²) अगर k = 0. हालाँकि, किसी के लिए भी k > 0, badsort(L, k) पहले उत्पन्न करता है P, के सभी क्रमपरिवर्तन की सूची L. तब, badsort गणना करता है badsort(P, k − 1), और क्रमबद्ध का पहला तत्व लौटाता है P. बनाने के लिए worstsort वास्तव में निराशावादी, k को एक गणना योग्य बढ़ते फ़ंक्शन के मान को सौंपा जा सकता है जैसे कि $f\colon \mathbb {N} \to \mathbb {N}$ (उदा f(n) = A(n, n), कहाँ A एकरमैन का कार्य है)। इसलिए, किसी सूची को मनमाने ढंग से बुरी तरह क्रमबद्ध करने के लिए, कोई निष्पादित करेगा worstsort(L, f) = badsort(L, f(length(L))), कहाँ length(L) में तत्वों की संख्या है L. परिणामी एल्गोरिदम में जटिलता है ${\textstyle \Omega \left(\left(n!^{(f(n))}\right)^{2}\right)}$, कहाँ $n!^{(m)}=(\dotso ((n!)!)!\dotso )!$ = का भाज्य n पुनरावृत्त m बार. पर्याप्त तेजी से बढ़ने वाले फ़ंक्शन को चुनकर इस एल्गोरिदम को जितना चाहें उतना अक्षम बनाया जा सकता है f.

स्लोसॉर्ट

एक अलग विनोदी सॉर्टिंग एल्गोरिदम जो बड़े पैमाने पर जटिलता प्राप्त करने के लिए एक गुमराह विभाजन और जीत रणनीति को नियोजित करता है।

Quantum bogosort

बोगोसॉर्ट पर आधारित एक काल्पनिक सॉर्टिंग एल्गोरिदम, कंप्यूटर वैज्ञानिकों के बीच मजाक के रूप में बनाया गया। एल्गोरिथ्म एन्ट्रापी के क्वांटम स्रोत का उपयोग करके अपने इनपुट का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करता है, जाँच करता है कि क्या सूची क्रमबद्ध है, और, यदि यह नहीं है, तो ब्रह्मांड को नष्ट कर देता है। यह मानते हुए कि कई-दुनिया की व्याख्या मान्य है, इस एल्गोरिदम के उपयोग के परिणामस्वरूप कम से कम एक जीवित ब्रह्मांड होगा जहां इनपुट को सफलतापूर्वक सॉर्ट किया गया था O(n) समय।

Miracle sort

एक सॉर्टिंग एल्गोरिदम जो जांच करता है कि कोई चमत्कार होने तक सरणी सॉर्ट की गई है या नहीं। यह क्रमबद्ध होने तक सरणी की लगातार जाँच करता रहता है, सरणी का क्रम कभी नहीं बदलता। क्योंकि क्रम कभी नहीं बदला जाता है, एल्गोरिथ्म में एक काल्पनिक समय जटिलता होती है O(∞), लेकिन यह अभी भी चमत्कार या एकल-घटना उथल-पुथल जैसी घटनाओं को सुलझा सकता है। इस एल्गोरिदम के कार्यान्वयन में विशेष सावधानी बरतनी चाहिए क्योंकि अनुकूलन करने वाले कंपाइलर इसे थोड़ी देर (सही) लूप में बदल सकते हैं। हालाँकि, सबसे अच्छा मामला है O(n), जो क्रमबद्ध सूची पर होता है।

यह भी देखें

• लास वेगास एल्गोरिथ्म
• कठपुतली प्रकार

बाहरी संबंध

• 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: 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