🧱 Unit 1 – Data Structures और Algorithms · Lesson 12
Sorting: Bubble, Selection, Insertion
Sorting क्या है?
Sorting मतलब data को ascending या descending order में लगाना – marks ऊपर से नीचे, नाम alphabetically। Sorted data में search बहुत तेज़ होता है (binary search के लिए यह ज़रूरी है)।
Bubble sort
पास-पास के elements की तुलना करें और ग़लत क्रम में हों तो swap करें। हर pass के बाद बचा हुआ सबसे बड़ा element अंत में अपनी सही जगह पर “bubble” हो जाता है।
Python
def bubble_sort(a):
n = len(a)
for i in range(n - 1): # passes
swapped = False
for j in range(n - 1 - i): # last i items already in place
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
print('Pass', i + 1, ':', a)
if not swapped: # already sorted -> stop early
break
nums = [8, 7, 13, 1, -9, 4]
bubble_sort(nums)Pass 1 : [7, 8, 1, -9, 4, 13]
Pass 2 : [7, 1, -9, 4, 8, 13]
Pass 3 : [1, -9, 4, 7, 8, 13]
Pass 4 : [-9, 1, 4, 7, 8, 13]
Pass 5 : [-9, 1, 4, 7, 8, 13]
Selection sort
List को बाएँ sorted हिस्से और दाएँ unsorted हिस्से में बाँटें। हर pass में unsorted हिस्से का सबसे छोटा element चुनकर उस हिस्से के आगे swap करें।
Python
def selection_sort(a):
n = len(a)
for i in range(n - 1):
m = i # index of smallest so far
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i] # put smallest at position i
print('Pass', i + 1, ':', a)
nums = [8, 7, 13, 1, -9, 4]
selection_sort(nums)Pass 1 : [-9, 7, 13, 1, 8, 4]
Pass 2 : [-9, 1, 13, 7, 8, 4]
Pass 3 : [-9, 1, 4, 7, 8, 13]
Pass 4 : [-9, 1, 4, 7, 8, 13]
Pass 5 : [-9, 1, 4, 7, 8, 13]
Insertion sort
हाथ में ताश के पत्ते लगाने जैसा: अगला element लें और उसे पहले से sorted बाएँ हिस्से में सही जगह insert करें, बड़े items को दाएँ खिसकाते हुए।
Python
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i] # card to insert
j = i - 1
while j >= 0 and a[j] > key: # shift bigger items right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
print('Pass', i, ':', a)
nums = [8, 7, 13, 1, -9, 4]
insertion_sort(nums)Pass 1 : [7, 8, 13, 1, -9, 4]
Pass 2 : [7, 8, 13, 1, -9, 4]
Pass 3 : [1, 7, 8, 13, -9, 4]
Pass 4 : [-9, 1, 7, 8, 13, 4]
Pass 5 : [-9, 1, 4, 7, 8, 13]
Strings / descending sort
Python
def bubble_desc(names):
n = len(names)
for i in range(n - 1):
for j in range(n - 1 - i):
if names[j] < names[j + 1]: # > becomes < for descending
names[j], names[j + 1] = names[j + 1], names[j]
return names
print(bubble_desc(['Ravi', 'Asha', 'Neha', 'Kabir']))['Ravi', 'Neha', 'Kabir', 'Asha']
Time complexity
n items के लिए simple sorts लगभग n×(n-1)/2 जोड़ों की तुलना करते हैं, जो n² की तरह बढ़ता है। Data दोगुना करने पर ये लगभग चार गुना धीमे हो जाते हैं।
Python
def count_bubble(a):
a = a[:]; comps = swaps = 0
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
comps += 1
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]; swaps += 1
return comps, swaps
for data in [[1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 1, 4, 5, 2]]:
print(data, '-> comparisons, swaps =', count_bubble(data))[1, 2, 3, 4, 5] -> comparisons, swaps = (10, 0)
[5, 4, 3, 2, 1] -> comparisons, swaps = (10, 10)
[3, 1, 4, 5, 2] -> comparisons, swaps = (10, 4)
तुलना
| Sort | Best | Average / Worst | Idea |
|---|---|---|---|
| Bubble | O(n) | O(n²) | Swap neighbours; largest bubbles to the end |
| Selection | O(n²) | O(n²) | Pick the smallest, put it in front |
| Insertion | O(n) | O(n²) | Insert each item into the sorted left part |
अक्सर पूछे जाने वाले प्रश्न (FAQ)
n elements के लिए bubble sort को कितने passes चाहिए?
ज़्यादा से ज़्यादा n-1 passes। swapped flag के साथ, किसी pass में swap न हो तो यह जल्दी रुक जाता है।
कौन सा sort सबसे कम swaps करता है?
Selection sort हर pass में ज़्यादा से ज़्यादा एक swap करता है, यानी कुल n-1 swaps तक।
लगभग sorted list के लिए कौन सा sort सबसे अच्छा है?
Insertion sort, क्योंकि हर नया item थोड़ी ही दूरी खिसकता है; इसका best case O(n) है।
