PricingLoginStart free
DSA Interview Prep · पाठ

Bubble Sort और Insertion Sort

दोनों द्विघात क्रमबद्धकरण एल्गोरिदम का कोड लिखिए, समझिए कि वे O(n²) क्यों हैं और वह एक स्थिति पहचानिए जिसमें insertion sort, merge sort से बेहतर होता है।

पाठ 1, कुल 4 में से13 चरण

Bubble Sort और Insertion Sort, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

O(n²) वाली सॉर्टिंग का अध्ययन क्यों करें

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

# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters

import time

def time_sort(sort_fn, data):
    import copy
    arr = copy.copy(data)
    t = time.perf_counter()
    sort_fn(arr)
    return time.perf_counter() - t

print('Small n: quadratic sorts are fine')

बबल सॉर्ट: अधिकतम को ऊपर लाना

बबल सॉर्ट ऐरे को बार-बार स्कैन करता है और गलत क्रम में मौजूद आस-पास के तत्वों की अदला-बदली करता है। हर पूरे पास के बाद सबसे बड़ा अक्रमित तत्व 'ऊपर उठकर' अंत में अपनी अंतिम स्थिति पर पहुँच जाता है। n-1 पास के बाद पूरा ऐरे क्रमबद्ध हो जाता है। इसका नाम इस बात से आया है कि बड़े तत्व बुलबुलों की तरह ऊपर तैरते हैं। इसका वर्णन करना सबसे आसान सॉर्टिंग एल्गोरिद्म है, लेकिन व्यवहार में इसका उपयोग बहुत कम होता है।

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):          # n-1 passes
        for j in range(n - 1 - i):  # inner loop shrinks
            if arr[j] > arr[j+1]:   # out of order
                arr[j], arr[j+1] = arr[j+1], arr[j]  # swap
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)  # [11, 12, 22, 25, 34, 64, 90]

बबल सॉर्ट में जल्दी बाहर निकलना

एक अनुकूलित बबल सॉर्ट में swapped ध्वज का उपयोग होता है: यदि किसी पूरे आंतरिक पास में एक भी अदला-बदली न हो, तो ऐरे पहले से क्रमबद्ध है और हम जल्दी बाहर निकल जाते हैं। इससे पहले से क्रमबद्ध इनपुट के लिए सर्वोत्तम स्थिति O(n) हो जाती है — बबल सॉर्ट का यही एक वास्तविक लाभ है। इस ध्वज के बिना यह हमेशा O(n²) तुलनाएँ करता है। बबल सॉर्ट में सुधारों के बारे में पूछे जाने पर साक्षात्कारकर्ता इसी जल्दी बाहर निकलने वाले अनुकूलन की जाँच करते हैं।

def bubble_sort_optimised(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:  # already sorted!
            print(f'Sorted after pass {i+1}')
            break

arr1 = [1, 2, 3, 4, 5]  # already sorted
bubble_sort_optimised(arr1)  # exits after 1 pass

बबल सॉर्ट की जटिलता का विश्लेषण

बबल सॉर्ट का बाहरी लूप n-1 बार चलता है। हर पास में आंतरिक लूप n-1-i बार चलता है: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 तुलनाएँ। इससे औसत और सबसे खराब स्थिति O(n²) मिलती है। जल्दी बाहर निकलने वाले ध्वज के साथ, क्रमबद्ध इनपुट के लिए सर्वोत्तम स्थिति घटकर O(n) हो जाती है। स्थान-जटिलता O(1) है — केवल अदला-बदली के लिए चरों की एक अस्थायी प्रति आवश्यक होती है। बबल सॉर्ट स्थिर है: समान तत्व अपना आपसी क्रम बनाए रखते हैं, क्योंकि हम केवल वास्तव में बड़े तत्वों की अदला-बदली करते हैं।

def bubble_sort_counted(arr):
    n = len(arr)
    swaps = comparisons = 0
    for i in range(n-1):
        for j in range(n-1-i):
            comparisons += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swaps += 1
    return comparisons, swaps

arr = [5, 4, 3, 2, 1]  # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}')  # 10, 10 for n=5

इन्सर्शन सॉर्ट: क्रमबद्ध हाथ बनाना

इन्सर्शन सॉर्ट ताश के पत्तों की गड्डी को हाथ में क्रमबद्ध करने जैसा है: अगला पत्ता (तत्व) उठाएँ और उसे बाईं ओर पहले से क्रमबद्ध पत्तों के बीच सही स्थान पर डालें। इनवेरिएंट यह है कि arr[0:i] हमेशा क्रमबद्ध रहता है। हर नए तत्व के लिए बड़े तत्वों को दाईं ओर खिसकाएँ, ताकि उसके लिए जगह बन सके। यह उसी स्थान पर काम करने वाला, स्थिर एल्गोरिद्म है जिसकी सबसे खराब स्थिति O(n²), लेकिन लगभग-क्रमबद्ध डेटा के लिए सर्वोत्तम स्थिति O(n) होती है।

def insertion_sort(arr):
    for i in range(1, len(arr)):  # start from second element
        key = arr[i]              # element to insert
        j = i - 1
        # Shift larger elements to the right
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key            # insert in correct position
    return arr

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr)  # [5, 6, 11, 12, 13]

इन्सर्शन सॉर्ट: चरण-दर-चरण

[3, 1, 4, 2] पर इन्सर्शन सॉर्ट का क्रम देखें: i=1, key=1, 3 को दाईं ओर खिसकाएँ → [1, 3, 4, 2]। i=2, key=4, कोई खिसकाव नहीं → कोई बदलाव नहीं। i=3, key=2, पहले 4 और फिर 3 को दाईं ओर खिसकाएँ → [1, 2, 3, 4]। हर तत्व की तुलना उसके बाईं ओर मौजूद तत्वों से तब तक की जाती है, जब तक उसका सही स्थान न मिल जाए। आंतरिक while लूप असाइनमेंट का उपयोग करके खिसकाव करता है (अदला-बदली से तेज़, क्योंकि एक खिसकाव में एक असाइनमेंट लगता है, जबकि अदला-बदली में तीन)।

def insertion_sort_trace(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]  # shift right (1 assignment)
            j -= 1
        arr[j+1] = key
        print(f'After inserting {key}: {arr}')

insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2]  (no change)
# After inserting 2: [1, 2, 3, 4]

लगभग-क्रमबद्ध डेटा पर इन्सर्शन सॉर्ट

इन्सर्शन सॉर्ट की सबसे बड़ी विशेषता इसकी O(n + उलट-क्रम युग्मों) जटिलता है। उलट-क्रम युग्म ऐसा युग्म (i,j) है जिसमें i < j लेकिन arr[i] > arr[j] होता है। केवल कुछ उलट-क्रम युग्मों वाले लगभग-क्रमबद्ध ऐरे के लिए इन्सर्शन सॉर्ट बेहद तेज़ होता है — व्यवहार में यह अपनी सरलता और कैश-अनुकूल पहुँच-पद्धति के कारण कभी-कभी मर्ज सॉर्ट से भी तेज़ होता है। पाइथन का टिमसॉर्ट छोटे उप-ऐरे पर इन्सर्शन सॉर्ट का उपयोग ठीक इसी कारण से करता है।

# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5]  # 4>3 is the only inversion

def count_ops(arr):
    arr = arr[:]
    ops = 0
    for i in range(1, len(arr)):
        key = arr[i]; j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]; j -= 1; ops += 1
        arr[j+1] = key
    return ops

print(count_ops([1,2,4,3,5]))  # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1]))  # 10 ops (reversed = worst case)

सॉर्टिंग में स्थिरता

कोई सॉर्टिंग एल्गोरिद्म स्थिर तब होता है, जब समान तत्व सॉर्टिंग के बाद अपना मूल आपसी क्रम बनाए रखते हैं। बबल सॉर्ट और इन्सर्शन सॉर्ट दोनों स्थिर हैं — वे कभी समान तत्वों की अदला-बदली नहीं करते। स्थिरता तब महत्वपूर्ण होती है, जब आप क्रमशः कई कुंजियों के आधार पर सॉर्ट करते हैं: पहले द्वितीयक कुंजी के आधार पर sort करें (स्थिर रूप से), फिर प्राथमिक कुंजी के आधार पर sort करें (स्थिर रूप से), ताकि समान प्राथमिक कुंजी वाले तत्वों में द्वितीयक कुंजी का क्रम बना रहे। मर्ज सॉर्ट भी स्थिर है; हीप सॉर्ट और क्विक सॉर्ट सामान्यतः स्थिर नहीं होते।

# Stable sort preserves order of equal elements
students = [
    ('Alice', 85),
    ('Bob',   92),
    ('Carol', 85),
    ('Dave',  78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
    print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol  => stable

बाइनरी खोज के रूप में इन्सर्शन सॉर्ट

इन्सर्शन सॉर्ट का आंतरिक लूप सही स्थान खोजने और तत्वों को खिसकाने, दोनों का काम करता है। स्थान खोजने के लिए बाइनरी खोज का उपयोग करके O(log i) तुलनाएँ की जा सकती हैं, लेकिन तत्वों को खिसकाने में अब भी O(i) समय लगेगा — इसलिए कुल जटिलता O(n²) ही रहती है। यह अनुकूलन तुलनाओं की संख्या घटाता है (महँगे तुलना-फलनों के लिए उपयोगी), लेकिन कुल कार्रवाइयों को नहीं घटाता। यह 'बाइनरी इन्सर्शन सॉर्ट' छोटे खंड आकारों के लिए टिमसॉर्ट में दिखाई देता है।

import bisect

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # Find insertion point in O(log i)
        pos = bisect.bisect_left(arr, key, 0, i)
        # Shift elements to make room: still O(i)
        arr[pos+1:i+1] = arr[pos:i]
        arr[pos] = key
    return arr

print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]

बबल बनाम इन्सर्शन: किसे कब उपयोग करें

साक्षात्कारों में यह तुलना आत्मविश्वास से बताइए: इन्सर्शन सॉर्ट, बबल सॉर्ट से स्पष्ट रूप से बेहतर है — दोनों की सबसे खराब स्थिति O(n²) और स्थान-जटिलता O(1) है, लेकिन इन्सर्शन सॉर्ट कम बार लिखता है (k उलट-क्रम युग्मों के लिए O(n+k), जबकि बबल सॉर्ट के लिए O(n²)), कैश के लिए अधिक अनुकूल है और छोटे n के लिए व्यावहारिक विकल्प है (टिमसॉर्ट इसका उपयोग करता है)। बबल सॉर्ट का एकमात्र वास्तविक लाभ शैक्षिक सरलता है। उत्पादन में हमेशा भाषा के अंतर्निहित sort का उपयोग करें।

# Summary: when to use quadratic sorts
# Use insertion_sort when:
#   - n <= 20 (small enough that O(n^2) is fine)
#   - data is nearly sorted (few inversions => fast)
#   - you need stable sort with O(1) space
#   - implementing a hybrid (like Timsort)

# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr))   # [1, 2, 5, 8, 9]
arr.sort()
print(arr)           # [1, 2, 5, 8, 9]

उलट-क्रम युग्मों की गणना एक माप के रूप में

किसी ऐरे में उलट-क्रम युग्मों की संख्या उन युग्मों (i,j) की संख्या के बराबर होती है जिनमें i < j लेकिन arr[i] > arr[j] होता है। इन्सर्शन सॉर्ट ठीक उतने ही खिसकाव करता है, जितने उलट-क्रम युग्म होते हैं — यह एक उपयोगी अंतर्दृष्टि है। उलट-क्रम युग्मों की कुशलता से गणना (O(n log n)) करने के लिए संशोधित मर्ज सॉर्ट आवश्यक है। सॉर्टिंग पर चर्चा के बाद साक्षात्कारकर्ता कभी-कभी आगे पूछते हैं, 'आपका एल्गोरिद्म उलट-क्रम युग्मों को कितना ध्यान में रखता है?'

# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                count += 1
    return count

print(count_inversions_naive([3, 1, 2]))  # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3]))  # 0: already sorted
print(count_inversions_naive([3, 2, 1]))  # 3: all pairs inverted

त्वरित जाँच

इस पाठ में Data Structures & Algorithms — Coding Interview Prep की अवधारणाओं की अपनी समझ जाँचें।

इंटरैक्टिव पाठ में इसका उत्तर दें

पाठ का पुनरावलोकन

इस पाठ में आपने सीखा: बबल सॉर्ट n-1 पास करता है, जिनमें हर बार वर्तमान अधिकतम तत्व अपनी अंतिम स्थिति तक पहुँचता है; इसकी सबसे खराब स्थिति O(n²), लेकिन जल्दी बाहर निकलने वाले ध्वज के साथ सर्वोत्तम स्थिति O(n) होती है, इन्सर्शन सॉर्ट वर्तमान key को सही क्रमबद्ध स्थान पर डालने के लिए तत्वों को दाईं ओर खिसकाता है और O(n + उलट-क्रम युग्मों) समय में चलता है, इसलिए लगभग-क्रमबद्ध डेटा के लिए सर्वोत्तम है, और दोनों एल्गोरिद्म स्थिर हैं, O(1) स्थान लेते हैं और उनकी सबसे खराब स्थिति O(n²) है — लेकिन सभी व्यावहारिक परिस्थितियों में बबल सॉर्ट के बजाय इन्सर्शन सॉर्ट को स्पष्ट रूप से प्राथमिकता दी जाती है। आगे हम शुरुआत से मर्ज सॉर्ट लागू करेंगे।

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम
30
पाठ
120
निःशुल्क सीखना शुरू करेंपूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Bubble Sort और Insertion Sort” पाठ निःशुल्क है?

हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “Bubble Sort और Insertion Sort” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Bubble Sort और Insertion Sort” में मैं क्या सीखूँगा?

दोनों द्विघात क्रमबद्धकरण एल्गोरिदम का कोड लिखिए, समझिए कि वे O(n²) क्यों हैं और वह एक स्थिति पहचानिए जिसमें insertion sort, merge sort से बेहतर होता है। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ DSA Interview Prep का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।

“Bubble Sort और Insertion Sort” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

  1. Bubble Sort और Insertion Sort
  2. Merge Sort: विभाजित करें, क्रमबद्ध करें, मिलाएँ
  3. Quick Sort और Pivot चयन
  4. तुलना-रहित क्रमबद्धकरण और Python का sort()
← DSA Interview Prep पर वापस जाएँ