बोगोसोर्ट

बोगोसोर्ट

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)$

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

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

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

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

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! के बराबर होती है . विनिमय की अपेक्षित संख्या तुलनाओं की अपेक्षित संख्या की तुलना में शीघ्रता से बढ़ती है, क्योंकि यदि तत्व क्रम में नहीं हैं, तो यह सामान्यतः केवल कुछ तुलनाओं के बाद ही अन्वेषण किया जाएगा, चाहे कितने भी तत्व हों लेकिन संग्रह में परिवर्तन का कार्य उसके आकार के समानुपाती होता है। सबसे निकृष्ट स्थिति में, तुलना और विनिमय दोनों की संख्या असीमित है, इसी कारण से कि एक उछाला गया सिक्का लगातार कितनी भी बार चित आ सकता है।

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

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

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

गोरोसोर्ट

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

बोजोबोगोसॉर्ट

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

बोगोसोर्ट

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

वर्स्टसोर्ट

एक निराशाजनक श्रेणीकरण कलन विधि जिसे सीमित समय में पूरा करने की आश्वासन दी जाती है; यद्यपि, इसकी विन्यास के आधार पर इसकी दक्षता मनमाने ढंग से खराब हो सकती है। वर्स्टसोर्ट कलन विधि वर्स्टसोर्ट श्रेणीकरण कलन विधि बैडसॉर्ट परआधारित है। बैडसॉर्ट कलन विधि दो मापदंडों को स्वीकार करता है: 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 को चुनकर इस कलन विधि को जितना चाहें उतना अक्षम बनाया जा सकता है।

स्लोसॉर्ट

एक अलग विनोदी श्रेणीकरण कलन विधि जो बड़े स्तर पर जटिलता प्राप्त करने के लिए एक पथभ्रष्ट विभाजन और जीत रणनीति को नियोजित करता है।

परिमाण बोगोसॉर्ट

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

कौतुक सॉर्ट

एक श्रेणीकरण कलन विधि जो जांच करता है कि कोई कौतुक होने तक सरणी क्रमबद्ध की गई है या नहीं की गई है । यह क्रमबद्ध होने तक सरणी की लगातार जाँच करता रहता है, सरणी का क्रम कभी नहीं बदलता है। क्योंकि क्रम कभी नहीं बदला जाता है, कलन विधि में 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