Overview
Bubble Sort adjacent elements को compare करता है और गलत order होने पर swap करता है। हर pass के बाद सबसे बड़ा pending element अंत में पहुंच जाता है।
Analogy
पानी में बुलबुले ऊपर आते हैं, वैसे ही बड़े values हर round में ऊपर (right side) जाते हैं।
Step-by-step
- list पर iterate करें और arr[j] को arr[j+1] से compare करें।
- अगर arr[j] > arr[j+1] हो तो swap करें।
- एक pass के बाद सबसे बड़ा element last position पर fix हो जाता है।
- अगले pass में range कम रखें क्योंकि tail already sorted है।
- अगर किसी pass में swap नहीं हुआ तो early stop करें।
Visual
Pass 1: [5,3,8,1,2] -> [3,5,1,2,8]; फिर हर pass में checking window छोटी होती जाती है।
Common mistakes
- inner-loop bound कम न करना।
- >= use करना और stability खो देना।
- zero swaps वाली pass पर break न करना।
Practice questions
- already sorted input पर early exit के साथ/बिना comparison count निकालें।
- explain करें Bubble Sort stable क्यों है।
- logic बदलकर descending sort करें।
Time
O(n²) worst/average, O(n) best with early exit