Bubble Sort Algorithm and Optimization

Bubble Sort ek simple comparison-based sorting algorithm hai. Iska naam isliye “Bubble” pada kyunki har pass me array ka sabse largest element hawa ke bubble ki tarah float karte hue array ke end (rightmost position) par pahunch jata hai.

Core Concept

Algorithm array me adjacent (bagal-bagal ke) elements ko compare karta hai. Agar left element right element se bada hota hai (A[j] > A[j+1]), toh unhe swap kar diya jata hai. N elements ke array ko completely sort karne ke liye maximum N - 1 passes ki zaroorat hoti hai.

Initial Array: [ 5, 1, 4, 2, 8 ]

Pass 1:
Compare 5 > 1 -> Swap: [ 1, 5, 4, 2, 8 ]
Compare 5 > 4 -> Swap: [ 1, 4, 5, 2, 8 ]
Compare 5 > 2 -> Swap: [ 1, 4, 2, 5, 8 ]
Compare 5 > 8 -> No Swap: [ 1, 4, 2, 5, | 8 ]  (8 is placed at correct spot)

Pass 2:
Compare 1 > 4 -> No Swap
Compare 4 > 2 -> Swap: [ 1, 2, 4, 5, 8 ]
Compare 4 > 5 -> No Swap: [ 1, 2, 4, | 5, 8 ]  (5 is placed)

Optimized Bubble Sort Algorithm

Standard bubble sort already sorted array par bhi O(n^2) comparisons karta hai. Isko optimize karne ke liye ek swapped boolean flag use karte hain. Agar kisi pass me koi bhi swap na ho, iska matlab array already sorted hai aur hum execution early terminate kar sakte hain.

BUBBLE_SORT_OPTIMIZED(A, N)
1. For i = 0 to N - 2 do:
2.     Set swapped = FALSE
3.     For j = 0 to N - i - 2 do:
4.         If A[j] > A[j+1] then:
5.             Swap(A[j], A[j+1])
6.             Set swapped = TRUE
7.     End For
8.     If swapped == FALSE then:
           Break  [Array is already sorted]
9. End For

Complexity and Properties

• Worst-case Time: O(n^2) – Jab array reverse sorted ho. Total comparisons = n(n-1)/2.
• Best-case Time (Optimized): O(n) – Jab array already sorted ho (only 1 pass with n-1 comparisons).
• Space Complexity: O(1) auxiliary space (in-place sorting algorithm).
• Stability: Stable sorting algorithm (equal elements ka relative order change nahi hota).

Agli post me hum cover karenge Selection Sort Algorithm and Step-by-Step Trace.