Overview
Bubble Sort adjacent elements compare karta hai aur galat order par swap karta hai. Har pass me sabse bada pending element end me chala jata hai.
Analogy
Water me bubbles upar aate hain, waise hi bade values har round me right side push hote hain.
Step-by-step
- List me loop chalao aur arr[j] ko arr[j+1] se compare karo.
- Agar arr[j] > arr[j+1] ho to swap karo.
- Ek pass ke baad sabse bada element end me lock ho jata hai.
- Next pass me range chhoti karo kyunki tail already sorted hai.
- Agar pass me koi swap na ho to early stop karo.
Visual
Pass 1: [5,3,8,1,2] -> [3,5,1,2,8]; phir har pass me scan window chhoti hoti jati hai.
Common mistakes
- Inner-loop bound reduce na karna.
- >= use karke stability break kar dena.
- 0 swaps wale pass par break na lagana.
Practice questions
- Already sorted input par early exit ke saath/without comparisons count karo.
- Explain karo Bubble Sort stable kyu hai.
- Logic change karke descending sort banao.
Time
O(n²) worst/average, O(n) best with early exit