Bubble Sort vs Selection Sort vs Insertion Sort
Compare bubble sort, selection sort, and insertion sort by operation, complexity, stability, adaptiveness, data movement, and practical use case.
Bubble sort, selection sort, and insertion sort all sort an array in place and all have O(n²) average and worst-case time. That shared complexity does not make them interchangeable.
The main difference is how they move values:
- Bubble sort swaps adjacent inversions until large values reach the right side.
- Selection sort selects the smallest remaining value and places it at the left boundary.
- Insertion sort takes the next value and inserts it into an already sorted prefix.
For most small or nearly sorted inputs, insertion sort is the most useful of the three. Selection sort is the best fit when minimizing writes matters. Bubble sort is primarily valuable for teaching adjacent swaps, inversions, stability, and early termination.
Quick Comparison
| Property | Bubble sort | Selection sort | Insertion sort |
|---|---|---|---|
| Main operation | Swap adjacent inversions | Select remaining minimum | Insert key into sorted prefix |
| Region completed by a pass | Right-side suffix | Left-side prefix | Left-side prefix |
| Best-case time | O(n) with early exit | O(n²) | O(n) |
| Average time | O(n²) | O(n²) | O(n²) |
| Worst-case time | O(n²) | O(n²) | O(n²) |
| Auxiliary space | O(1) | O(1) | O(1) |
| Standard stability | Stable | Unstable | Stable |
| Adaptive | Yes with early exit | No | Yes |
| Data movement | Up to O(n²) swaps | At most n - 1 swaps | Up to O(n²) shifts |
| Online | No | No | Yes |
| Strongest use case | Teaching adjacent exchanges | Limiting swap count | Small or nearly sorted arrays |
The table separates comparison count from data movement. Selection sort can perform fewer writes while still making O(n²) comparisons. Insertion sort can also be quadratic, but it does much less work when values are already close to their final positions.
How Each Algorithm Organizes the Array
Bubble sort grows a sorted suffix
Bubble sort compares neighbors from left to right. When the left value is greater, the pair swaps. After one complete pass, the largest remaining value has reached the right boundary.
unsorted region | sorted suffixIts useful invariant is that the suffix after the current boundary is already final. An optimized implementation stops when a complete pass makes no swaps.
Read the Bubble Sort Algorithm tutorial for its dry run, correctness argument, and Rust and Go implementations.
Selection sort grows a sorted prefix
Selection sort scans the entire unsorted region for its smallest value. It then swaps that minimum into the first unsorted position.
sorted prefix | unsorted regionIts invariant is that every value in the sorted prefix is in its final position and no greater than the values that remain. Input order does not shorten the scan, so its best case remains O(n²).
Read the Selection Sort Algorithm tutorial for the implementation and proof.
Insertion sort extends a sorted prefix
Insertion sort treats the first element as sorted. It saves the next value as a key, shifts larger prefix values right, and inserts the key into the gap.
sorted prefix | next key | unsorted suffixIts work depends on displacement and inversions. A key already in the correct relative position needs one comparison and no shift, which gives insertion sort its O(n) best case.
Read the Insertion Sort Algorithm tutorial for its shift-based implementation, inversion analysis, and binary-search variation.
Bubble Sort vs Selection Sort
Bubble sort and selection sort both use nested passes, but a pass has a different guarantee.
Bubble sort guarantees that one large value reaches the right side. It may swap many times during the pass. Selection sort guarantees that one minimum reaches the left side and normally performs no more than one swap during the pass.
Choose between them based on behavior rather than their shared O(n²) bound:
| Requirement | Better fit | Reason |
|---|---|---|
| Minimize swaps or array writes | Selection sort | At most one swap per pass |
| Preserve equal-key order | Bubble sort | Strict adjacent swaps are stable |
| Stop quickly on sorted input | Bubble sort | A no-swap pass proves completion |
| Predictable comparison count | Selection sort | Always n(n - 1) / 2 comparisons |
| Teach inversions | Bubble sort | Every swap removes one inversion |
Selection sort normally wins on write count. Optimized bubble sort wins on adaptiveness and stability. For general application code, neither is competitive with a standard-library sort.
Insertion Sort vs Bubble Sort
Both algorithms can be stable, adaptive, in place, and O(n) on sorted input. Their movement is different.
Bubble sort repeatedly exchanges adjacent values across full passes. A small value near the end can move left only one position per left-to-right pass. Insertion sort saves that value once and shifts the larger prefix values right during the same insertion.
This usually makes insertion sort the better small-array algorithm. Bubble sort remains useful when the relationship between adjacent swaps and inversions is specifically important.
Insertion Sort vs Selection Sort
Both grow a sorted prefix, but insertion sort places the next input value while selection sort searches for the smallest remaining value.
Insertion sort is adaptive: an already sorted input needs linear work. Selection sort still scans every remaining suffix and therefore performs the same comparison count regardless of input order.
Selection sort has one advantage when writes are unusually expensive. It performs at most n - 1 swaps. Insertion sort may shift O(n²) values in a reverse-sorted array.
Why the Same O(n²) Complexity Produces Different Behavior
Big-O notation describes growth, not the exact operations performed on a particular input.
- Bubble sort's swaps equal the number of inversions, but its passes may still repeat comparisons.
- Selection sort performs exactly
n(n - 1) / 2comparisons in its standard form. - Insertion sort performs work proportional to the number of values each key crosses; it can be described as O(n + I), where
Iis the inversion count.
This is why insertion sort can perform well on nearly sorted arrays even though all three algorithms have O(n²) worst-case time.
Stability and Equal Values
A stable sort preserves the original order of records with equal keys.
Bubble sort is stable when it swaps only if left > right. Equal adjacent values do not cross.
Insertion sort is stable when it shifts only values strictly greater than the key. The new key stays after equal values already present in the prefix.
Standard selection sort is unstable. A distant swap can move one equal record across another. A stable selection-sort variation can shift values instead, but that removes the low-write behavior that distinguishes the standard algorithm.
Which Algorithm Should You Choose?
Use insertion sort when the collection is small, already partly ordered, arriving incrementally, or used as the small-partition base case inside a faster hybrid sorting algorithm.
Use selection sort when a teaching implementation needs predictable scans or when reducing writes is more important than reducing comparisons.
Use bubble sort when teaching adjacent comparison, stability, early exit, loop invariants, or the connection between swaps and inversions.
For large general-purpose inputs, use none of them. Rust, Go, and other languages provide optimized standard-library sorting functions with better asymptotic and practical performance.
Bottom Line
Bubble sort, selection sort, and insertion sort share O(1) auxiliary space and O(n²) worst-case time, but optimize different ideas:
- Bubble sort makes adjacent disorder visible.
- Selection sort limits swaps.
- Insertion sort exploits existing order.
That division gives each tutorial a clear job. The comparison lives here; implementation, correctness, dry runs, and algorithm-specific edge cases remain in the three dedicated guides.
Sources
Frequently Asked Questions
What is the difference between bubble sort and selection sort?
Bubble sort repeatedly swaps adjacent inverted values and moves a large value toward the right boundary on each pass. Selection sort scans the unsorted region, selects its minimum, and moves that value to the left boundary with at most one swap per pass. Optimized bubble sort is adaptive and stable; standard selection sort is neither, but selection sort usually performs substantially fewer writes.
Which is better, bubble sort or selection sort?
Selection sort is preferable when minimizing swaps or writes matters. Optimized bubble sort is preferable as a teaching example when stability, adjacent exchanges, inversion counting, or early exit on sorted input is the lesson. Neither is a good default for large application datasets.
How is insertion sort different from bubble sort?
Insertion sort removes the next key and shifts larger values in the sorted prefix to open its final position. Bubble sort swaps adjacent inverted pairs across complete passes. Both are stable, adaptive, in-place, and quadratic in the worst case, but insertion sort is generally more useful for small or nearly sorted arrays.
Which of bubble sort, selection sort, and insertion sort is fastest?
All three have quadratic average and worst-case time. Insertion sort is usually the practical winner for small or nearly sorted inputs because its work tracks how far values are displaced. Optimized bubble sort can be linear on sorted input but performs many swaps. Selection sort always performs a quadratic number of comparisons but limits swaps to at most n minus 1.
Are bubble sort, selection sort, and insertion sort in place?
Yes. Their standard array implementations use O(1) auxiliary space. Bubble sort and insertion sort are stable when implemented with strict comparisons. Standard swap-based selection sort is not stable.
Follow on Google
Add as a preferred source in Search & Discover
Add as preferred source
Krunal Kanojiya
Technical Content Writer
Krunal is a technical content writer at Lucent Innovation and a former full-stack developer with professional technology experience since 2021. He publishes source-backed, practical guides on AI engineering, RAG, vector search, data engineering, algorithms, and software development.