एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

बोगोसॉर्ट (Bogosort)

हमने कई तरह की समस्याओं के लिए क्रमबद्ध सूचियों का उपयोग किया है। अक्सर बिल्ट-इन फ़ंक्शनों का सहारा लेकर एरेज़ को sort भी किया है। लेकिन ये साफ़ नहीं होता कि वे बिल्ट-इन फ़ंक्शन अंदर से कैसे काम करते हैं। इस अध्याय में, हम कुछ लोकप्रिय सॉर्टिंग एल्गोरिदम पर बात करेंगे जो अलग-अलग प्रयोजनों के लिए इस्तेमाल किए जाते हैं—यह निर्भर करता है कि ज़रूरत क्या है।
इसमें सबसे पहले हम जिस एल्गोरिदम पर चर्चा करने जा रहे हैं, वह अब तक के सबसे “बेढंगे” सॉर्टिंग एल्गोरिदमों में से एक है: Bogosort। इसे वास्तविक दुनिया में कभी इस्तेमाल नहीं किया जाता, और आप जल्द ही समझ जाएँगे कि क्यों।
मान लें हमारे पास n संख्याएँ हैं। यह एल्गोरिदम उन संख्याओं को लगातार बेतरतीब तरीके से shuffle करता रहता है और फिर हर बार चेक करता है कि सूची क्रमबद्ध हुई या नहीं:
from random import shuffle

a = [3, 1, -2, 5, 6]            # प्रारंभिक संख्याएँ
while True:                     # तब तक दोहराएँ जब तक सूची क्रमबद्ध न हो जाए
    is_sorted = True
    for i in range(1, len(a)):  # जाँचने वाला लूप: क्या सूची क्रमबद्ध है?
        if a[i] < a[i-1]:       # यदि कोई तत्व अपने पिछले तत्व से छोटा है, तो यह क्रमबद्ध नहीं
            is_sorted = False   # is_sorted को False कर दें और लूप से बाहर निकलें
            break
    if is_sorted:               # यदि सूची क्रमबद्ध है => अनंत लूप से बाहर निकलें
        break
    else:                       # नहीं तो सूची को फिर से बेतरतीब करें
        shuffle(a)

print(a)                        # अंत में सूची को प्रिंट करें
यह एल्गोरिदम पूरी तरह से यादृच्छिक (random) है, इसलिए इसका चलना अनंत समय तक भी खिंच सकता है। ज़ाहिर है, ऐसे एल्गोरिदम को वास्तविक प्रणालियों में उपयोग करना बेहद ख़तरनाक और अदक्ष होगा।
अब आपको यह निकालना है कि Bogosort एल्गोरिदम को किसी सूची को आख़िरकार क्रमबद्ध ढंग से ढूँढ़ने (या कहें, पाने) में कितने iteration लगेंगे।

इनपुट

इनपुट की पहली पंक्ति में एक अकेला पूर्णांक n होता है (1 ≤ n ≤ )।
अगली पंक्ति में n अंतर-मुक्त जगह से अलग हुई संख्याएँ दी जाती हैं (जहाँ )।

आउटपुट

प्रोग्राम को वह संख्या प्रिण्ट करनी है, जो दर्शाएगी कि Bogosort एल्गोरिदम को सूची को क्रमबद्ध पाने में कितने iteration लगाने पड़े।

उदाहरण

इनपुट
आउटपुट
5 5 -1 2 3 9
10

स्पष्टीकरण

आउटपुट में दिखाई गई संख्या 10 बस एक नमूना है—वह कभी 2 हो सकती थी, या 200 भी। एक ही इनपुट के साथ बार-बार चलाने पर भी आपको अलग-अलग परिणाम मिल सकते हैं।
 

अन्य अजीबोगरीब सॉर्टिंग एल्गोरिदम

आप नीचे दिए गए यूट्यूब वीडियो में (जो Ardens द्वारा बनाया गया है) अन्य विज़ुअलाइज़्ड सॉर्टिंग एल्गोरिदम देख सकते हैं।
Video preview
Ardens: 10 FORBIDDEN Sorting Algorithms
 

Constraints

Time limit: 60 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue