Bubble sort, selection sort, insertion sort — O(n²), when insertion sort wins

3.6.1 · Coding › Sorting & Searching

Intuition Badi picture

Teeno quadratic ( $O (n^{2})$ ) comparison sorts hain. Ye aapas mein is baat mein differ karte hain ki har pass mein kya kaam karte hain aur, sabse zaroori, jab data pehle se almost sorted ho tab kaise behave karte hain.

Bubble = baar baar adjacent out-of-order pairs ko swap karo; sabse bada element end ki taraf "bubble" karta hai.
Selection = unsorted part scan karo minimum dhundhne ke liye, phir use sahi jagah rakh do. Comparisons ki count hamesha same rehti hai.
Insertion = agla element lo aur use left slide karo already-sorted prefix mein sahi spot par. Bilkul haath mein cards sort karne jaisa behave karta hai.

Headline result: Insertion sort chhote ya nearly-sorted arrays par jeet jaata hai kyunki ye pass ko jaldi khatam kar sakta hai — jab array pehle se sorted ho tab ye $O (n)$ kaam karta hai.

YE SAB $O (n^{2})$ KYU HAIN? (Scratch se derivation)

HUM KYA COUNT KARTE HAIN: comparisons ki sankhya + element moves ki sankhya, input size $n$ ke function ke roop mein.

Selection sort — exact count (hamesha same)

YE KAISE CHALTA HAI: har position $i$ ke liye $0$ se $n - 2$ tak, baaki scan karo minimum dhundhne ke liye.

Pass $i = 0$ : $n - 1$ elements se compare karo.
Pass $i = 1$ : $n - 2$ elements se compare karo.
… last pass tak: $1$ comparison.

Total comparisons: $C = (n - 1) + (n - 2) + \dots + 1 = \sum_{k = 1}^{n - 1} k = \frac{( n - 1 ) n}{2}$

Ye sum kyun? Gauss trick: pehle aur aakhri term ko pair karo $(n - 1) + 1 = n$ , doosra aur doosra-aakhri $(n - 2) + 2 = n$ … aisi $\frac{n - 1}{2}$ pairs hain jo har ek $n$ tak jodi jaati hain, jisse $\frac{n ( n - 1 )}{2}$ milta hai.

Kyunki scan kabhi jaldi nahi rukti, $C = \frac{n ( n - 1 )}{2} = O (n^{2})$ best, worst, aur average teeno cases mein. Swaps, lekin, zyada se zyada $n - 1$ hain (ek per pass) — selection sort writes kam karta hai.

Bubble sort — worst case

KAISE: array mein baar baar pass karo adjacent inversions ko swap karte hue. Pass $k$ ke baad, sabse bade $k$ elements end mein lock ho jaate hain.

Worst case (reverse-sorted): pass $k$ mein $n - k$ comparisons hote hain: $C = \sum_{k = 1}^{n - 1} (n - k) = \frac{n ( n - 1 )}{2} = O (n^{2})$

"Kya maine swap kiya?" flag ke saath, best case (pehle se sorted) = ==ek pass, $n - 1$ comparisons, $O (n)$ == — lekin worst case mein bahut saare swaps karta hai ( $O (n^{2})$ ).

Insertion sort — best vs worst

KAISE: sorted prefix A[0..i-1] rakho. A[i] lo, bade elements ko right shift karo, use drop karo.

Best case (pehle se sorted): har naya element apne left neighbour se $\geq$ hai, toh inner loop turant ruk jaata hai → $1$ comparison per element → $n - 1$ comparisons → == $O (n)$ ==.
Worst case (reverse-sorted): element $i$ apne saare $i$ predecessors ko cross karta hai: $C = \sum_{i = 1}^{n - 1} i = \frac{n ( n - 1 )}{2} = O (n^{2})$

Moves ki sankhya array mein inversions ki sankhya ke barabar hoti hai — yahi woh gehri wajah hai ki insertion sort nearly-sorted data par itna fast hai.

Formula Cost summary

	Comparisons (best / avg / worst)	Swaps/Moves (worst)	Stable?
Bubble (w/ flag)	$n - 1$ / $O (n^{2})$ / $\frac{n ( n - 1 )}{2}$	$O (n^{2})$	✅
Selection	$\frac{n ( n - 1 )}{2}$ always	$n - 1$	❌ (default)
Insertion	$n - 1$ / $O (n^{2})$ / $\frac{n ( n - 1 )}{2}$	$O (n^{2})$ but $Θ (inversions)$	✅

Figure — Bubble sort, selection sort, insertion sort — O(n²), when insertion sort wins

Key insight: inversions

Worked examples

Common mistake Galat ideas ko steel-man karna

❌ "Bubble aur insertion dono $O (n^{2})$ hain, toh dono equally fast hain." Kyun sahi lagta hai: same Big-O worst case. Fix: Big-O best/average behaviour aur constant factors chhupaata hai. Insertion average par kahin kam moves karta hai aur real libraries mein standard "small-array" sort hai (jaise Timsort, introsort chhote chunks ke liye insertion par fall back karte hain). Bubble practically almost kabhi use nahi hota.

❌ "Selection sort fast hai kyunki ye kam swaps karta hai." Kyun sahi lagta hai: sirf $n - 1$ swaps — sach aur useful jab writes expensive hoon (jaise flash memory). Fix: ye phir bhi $\frac{n ( n - 1 )}{2}$ comparisons har baar karta hai, toh nearly-sorted data par ye strictly insertion se badtar hai.

❌ "Selection sort stable hai." Kyun sahi lagta hai: ye gentle lagta hai. Fix: ek door ke minimum ko jagah par swap karna use ek equal key se aage kud sakta hai, stability tod ke. Insertion aur bubble (shift karo, long-swap mat karo) naturally stable hain.

❌ "Insertion $O (n)$ hai kyunki inner loop kabhi kabhi jaldi ruk jaata hai." Fix: sirf best/near-sorted case mein. Reverse-sorted input full shifts force karta hai → $O (n^{2})$ .

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ki tum playing cards ko haath mein sort kar rahe ho.

Insertion: tum cards ek ek karke uthate ho aur har ek ko sahi jagah slide karte ho un cards ke beech jo tum pehle se pakde ho. Agar wo almost order mein the, toh tum muskil se kuch move karte ho — super quick!
Selection: tum table par saare cards dekhte ho, sabse chhota dhundhte ho, rakhte ho, phir baaki sabko phir se dekhte ho, agla sabse chhota dhundhte ho… Tum hamesha sab kuch dekhte ho, chahe wo pehle se sorted hi kyun na hon.
Bubble: tum kisi bhi do neighbours ko jo galat order mein hain swap karte rehte ho, left se right sweep karte hue, jab tak kuch swap karne ki zaroorat na ho. Bade cards dheere dheere end par "float" karte hain. Trick: insertion sort ek achhe tarike se lazy hai — jab card pehle se sahi jagah par ho tab wo usi waqt ruk jaata hai. Isliye ye jeet jaata hai jab cheezein almost tidy hoti hain.

#flashcards/coding

Why is selection sort always

Θ (n^{2})

even on a sorted array?

Iska inner scan minimum dhundhne ke liye kabhi jaldi nahi rukta — ye hamesha

\frac{n ( n - 1 )}{2}

comparisons karta hai chahe input ka order kuch bhi ho.

What is the best-case time of insertion sort and when does it occur?

O (n)

, jab array pehle se (almost) sorted ho — har element sirf apne left neighbour ko check karta hai aur ruk jaata hai.

Insertion sort's number of moves equals what quantity?

Array mein inversions ki sankhya (out-of-order pairs).

Which two of the three sorts are naturally stable?

Bubble aur insertion (ye adjacent elements shift karte hain); selection by default stable nahi hai.

Which sort minimises the number of writes/swaps, and why might that matter?

Selection sort — sirf

n - 1

swaps. Useful jab writes expensive hoon (jaise flash memory wear).

When does insertion sort beat bubble and selection in practice?

Chhote ya nearly-sorted arrays par — ye adaptive hai, isliye libraries ise faster sorts ke andar tiny sub-arrays ke liye use karti hain.

Derive selection sort's comparison count.

(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}

Gauss pairing se.

What single optimisation makes bubble sort

O (n)

in the best case?

Ek "swapped?" flag: agar ek poora pass koi swap nahi karta, array sorted hai — ruk jao.

Reverse-sorted input: how many comparisons does insertion sort do?

\sum_{i = 1}^{n - 1} i = \frac{n ( n - 1 )}{2}

, iska worst case

O (n^{2})

Why is bubble sort rarely used despite the same Big-O as insertion?

Ye average par kahin zyada swaps karta hai aur koi real advantage nahi hai; insertion ke better constants hain aur ye standard small-array sort hai.

Connections

Merge Sort — $O (n lo g n)$ divide-and-conquer; chhote chunks ke liye insertion sort use karta hai.
Quicksort / Introsort — size threshold ke neeche insertion sort par switch karte hain.
Timsort — real-world hybrid jo insertion sort + merge par bana hai, existing runs exploit karta hai.
Inversions and Counting — "kitna unsorted" hai array ka formal measure.
Big-O Notation — kyun worst-case ke aage best/average/worst sab matter karte hain.
Stability in Sorting — equal keys ka order preserve karna.
Lower Bound for Comparison Sorts — $Ω (n lo g n)$ barrier jo ye quadratic sorts nahi tod paate.