Bubble Sort vs Selection Sort vs Insertion Sort
Introduction
- Are you confused about which sorting algorithm is better: Bubble Sort, Selection Sort or Insertion Sort?
- Below is the comparison table between these algorithms:
Sorting Algorithms Comparison
| # | Aspect | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|---|
| 1 | Best Case | O(n) → Fast if array is already sorted | O(n²) → No improvement in best case | O(n) → Very efficient when array is nearly sorted |
| 2 | Average Case | Θ(n²) | Θ(n²) | Θ(n²) |
| 3 | Worst Case | Θ(n²) | Θ(n²) | Θ(n²) |
| 3 | Stability | Stable → Equal elements keep order | Not Stable → Equal elements may swap order | Stable → Equal elements keep order |
| 4 | Adaptive | Yes (Improves if list nearly sorted) | No | Yes (Efficient for partially sorted data) |
| 5 | Swaps | Many → Makes it slow | Few → Makes it faster | Moderate → Balanced performance |
| 6 | Comparisons | High → Slower | High → Slower | Less in sorted lists → Faster |
| 7 | Practical Use | Rarely used (too slow) | Useful for small datasets | Good for small or nearly sorted datasets |
| 8 | Overall Efficiency | Poor → Slow in most cases | Better than Bubble but still slow | Best among the three for small/nearly sorted data |
- From above, its clear that Insertion Sort is much better as compared to Bubble Sort and Selection Sort.
Why Insertion Sort is better for smaller list as compared to Bubble Sort or Selection Sort ?
-
Lower Overhead
- Insertion Sort has very little overhead (extra burden) — no extra swaps or comparisons beyond what’s necessary.
- This makes it faster in practice for small datasets, even though the time complexity is still
O(n²).
-
Adaptive Nature
- Insertion Sort is adaptive, meaning it performs fewer operations if the list is already partially sorted.
- Example: If the array is almost sorted, insertion sort will approach
O(n)instead ofO(n²).
-
Fewer Comparisons than Bubble/Selection
- Bubble Sort makes many unnecessary swaps, and Selection Sort makes unnecessary comparisons.
- Insertion Sort minimizes both for small arrays, making it more efficient.
-
Efficient in Practice (Cache Friendly)
- Works in-place with sequential memory access.
- CPU cache handles it efficiently, so execution speed is higher.
-
Simple Implementation
- Very simple to implement with fewer lines of code.
- For small arrays, the simplicity often outperforms complex algorithms.
-
Used in Real-World Hybrid Algorithms
- Many modern sorting algorithms (like Timsort in Python and Java) switch to insertion sort when dealing with small subarrays.
- It’s faster in practice for those cases.
Key Reason: Insertion Sort is adaptive, has less overhead, and runs very fast on small or nearly sorted datasets, making it better than Bubble or Selection Sort in such cases.
Help Us Get Better Every Day
Your feedback helps us grow! If there's anything we can fix or improve, please let us know.
We’re here to make our tutorials better based on your thoughts and suggestions.
