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

बबल सॉर्ट (Bubble Sort)

न्यूमरिकल मानों की एक array (जैसे n पूर्णांकों की) को हमें बढ़ते क्रम में सॉर्ट करना है। बबल सॉर्ट एक प्रसिद्ध और सीधा-सा एल्गोरिथ्म है (हालाँकि यह तेज़ नहीं है—उत्पादकता के लिहाज़ से आम तौर पर दूसरे सॉर्टिंग एल्गोरिथ्म इस्तेमाल किए जाते हैं)।
Video preview
बबल सॉर्ट में, हम दिए गए array पर कई बार लूप चलाते हैं और हर ऐसे जोड़े (पड़ोसी एलिमेंट) को स्वैप (swap) करते हैं जो सही क्रम में नहीं होते। यानी यदि हो, तो इन दोनों को अदला-बदली करके सुनिश्चित किया जाता है कि array बढ़ते क्रम में रहे।
व्यवहारिक रूप से देखें तो, हमारे पास आरंभिक array a है (उदाहरण के लिए [4, 1, -1, 0, 2, 8])। सबसे पहले, हम पहले दो एलिमेंट देखते हैं। अगर वे क्रम में नहीं हैं, तो हम उन्हें स्वैप (बदल) देते हैं (इस उदाहरण में [1, 4, -1, 0, 2, 8])। उसके बाद अगले दो एलिमेंट पर जाते हैं। अगर वे क्रम में नहीं हैं, तो फिर स्वैप (इस उदाहरण में [1, -1, 4, 0, 2, 8])। यह सिलसिला array के अंत तक चलता है (इस उदाहरण में [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → कोई बदलाव नहीं → काम ख़त्म)।
इसके बाद लूप दोबारा आरंभ होता है। फिर से हम पहले जोड़े को देखते हैं, ज़रूरत पड़ने पर स्वैप करते हैं, फिर अगले जोड़े पर जाते हैं, और इस क्रम में array के अंत तक पहुँचा जाता है। उदाहरण में, यह [1, -1, 0, 2, 4, 8] से शुरू होकर आगे इस तरह बदलेगा: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → कोई बदलाव नहीं।
यह प्रक्रिया तब तक चलती रहती है जब तक पूरा array पूरी तरह से सॉर्ट न हो जाए:
a = [...]
while True:                                 # array के पूरी तरह सॉर्ट होने तक चलाएं
    is_sorted = True                        # कोई बदलाव हुआ तो इसे False किया जाएगा
    for i in range(len(a) - 1):             # 0 ... n-2 तक लूप
        if a[i] > a[i + 1]:                 # अगर कोई एलिमेंट अपने पड़ोसी से बड़ा है
            is_sorted = False               # => array अभी सॉर्ट नहीं है
            a[i], a[i + 1] = a[i + 1], a[i] # a[i] और a[i+1] को स्वैप करें
    
    if is_sorted:                           # अगर array अब सॉर्ट है, लूप तोड़ दें
        break
print(a)
इसे बेहतर बनाने के लिए हम एक छोटा-सा अनुकूलन (optimization) कर सकते हैं ताकि गैर-ज़रूरी चरणों को बचाया जा सके:
  • जब एक बार लूप चल जाता है, तो सबसे बड़े एलिमेंट्स अंत में पहुँच जाते हैं। यानी k पास के बाद, आख़िरी के k एलिमेंट निश्चित रूप से सही जगह पर पहुँच चुके होते हैं। इसलिए, हम आंतरिक लूप में उन्हें छोड़ सकते हैं:
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = आंतरिक लूप के लिए ऊपरी सीमा
    is_sorted = True                        # कोई बदलाव हुआ तो इसे False किया जाएगा
    for i in range(u):                      # 0 ... u-1 तक लूप
        if a[i] > a[i + 1]:                 # अगर कोई एलिमेंट अपने पड़ोसी से बड़ा है
            is_sorted = False               # => array अभी सॉर्ट नहीं है
            a[i], a[i + 1] = a[i + 1], a[i] # a[i] और a[i + 1] को स्वैप करें
    
    if is_sorted:                           # अगर array सॉर्ट हो गया तो लूप छोड़ दें
        break
print(a)
बबल सॉर्ट का सबसे ख़राब मामला (worst-case scenario) तब होता है जब सारे एलिमेंट उल्टे क्रम में (descending order) होते हैं। इस स्थिति में, इस एल्गोरिथ्म को ऑपरेशन्स करने पड़ जाते हैं, जो तेज़ सॉर्टिंग एल्गोरिथ्म (जिन्हें हम आगे पढ़ेंगे) की तुलना में काफ़ी ज़्यादा है।
चलिए इस एल्गोरिथ्म को कुछ अलग-अलग arrays पर चलाने का तरीका देखें:
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ swap (स्वैप) ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ swap (स्वैप) ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ swap (स्वैप) ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ swap (स्वैप) ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ swap (स्वैप) ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ swap (स्वैप) ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ swap (स्वैप) ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ swap (स्वैप) ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ कोई बदलाव नहीं
ऐक्ट्रा करिक्यूलर (दिलचस्प वीडियो)
YouTube पर Lines That Connect द्वारा एक बेहतरीन वीडियो बनाया गया है, जिसमें बबल सॉर्ट एल्गोरिथ्म के बारे में गहराई से बताया गया है और यह समझाया गया है कि एल्गोरिथ्म चलने पर जो आकृति बनती है, वह कैसे बनती है।
Video preview
वीडियो: Lines That Connect – बबल सॉर्ट कर्व।

चुनौती (Challenge)

n प्रतिभागी किसी प्रतियोगिता में हिस्सा ले रहे हैं। आपको उन्हें उनके कद के आधार पर बढ़ते क्रम में व्यवस्थित करना है। हर कदम पर आप केवल दो पड़ोसी प्रतिभागियों को अदला-बदली करने का निर्देश दे सकते हैं। आपके पास अधिक समय नहीं है, इसलिए आप इसे यथासंभव कुशल तरीक़े से करना चाहते हैं।
आपने तय किया है कि एक प्रोग्राम लिखा जाए, जो उन प्रतिभागियों के इंडेक्स प्रिंट करे जिनको स्वैप (swap) करना चाहिए। इंडेक्सिंग 0 से शुरू होगी।

इनपुट

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

आउटपुट

प्रोग्राम को उन प्रतिभागियों के जोड़े के इंडेक्स प्रिंट करने चाहिए जिन्हें स्वैप करने की ज़रूरत है। हर जोड़े को अलग पंक्ति में प्रिंट किया जाए। यदि एक से ज़्यादा सही विकल्प हों, तो कोई भी स्वीकार्य है।

उदाहरण

Input
Output
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

व्याख्या

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

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