116

I'm trying to understand a few sorting algorithms, but I'm struggling to see the difference in the bubble sort and insertion sort algorithm.

I know both are O(n2), but it seems to me that bubble sort just bubbles the maximum value of the array to the top for each pass, while insertion sort just sinks the lowest value to the bottom each pass. Aren't they doing the exact same thing but in different directions?

For insertion sort, the number of comparisons/potential swaps starts at zero and increases each time (ie 0, 1, 2, 3, 4, ..., n) but for bubble sort this same behaviour happens, but at the end of the sorting (ie n, n-1, n-2, ... 0) because bubble sort no longer needs to compare with the last elements as they are sorted.

For all this though, it seems a consensus that insertion sort is better in general. Can anyone tell me why?

Edit: I'm primarily interested in the differences in how the algorithms work, not so much their efficiency or asymptotic complexity.

4
  • 1
    This is well documented elsewhere: see, for example, en.wikipedia.org/wiki/Sorting_algorithm. Rather pointless to duplicate here and a good answer will be expansive.
    – Bathsheba
    Commented Jun 24, 2013 at 8:07
  • 1
    @Bathsheba 75 people who have upvoted and 88k who have viewed the question seem to disagree ; )
    – parsecer
    Commented Mar 5, 2020 at 10:57
  • @parsecer: Ha! Now I'm going to have to review the answers. The current highest upvoted answer is useful; not sure about the others. Here's to some rep points lost by answer downvoting. The assertion "That's why insertion sort is faster than bubble sort" in the accepted answer is not necessarily true.
    – Bathsheba
    Commented Mar 5, 2020 at 10:59
  • 1
    @Bathsheba Oh no
    – parsecer
    Commented Mar 5, 2020 at 11:03

18 Answers 18

159

Insertion Sort

After i iterations the first i elements are ordered.

In each iteration the next element is bubbled through the sorted section until it reaches the right spot:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

The 4 is bubbled into the sorted section

Pseudocode:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Bubble Sort

After i iterations the last i elements are the biggest, and ordered.

In each iteration, sift through the unsorted section to find the maximum.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

The 5 is bubbled out of the unsorted section

Pseudocode:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Note that typical implementations terminate early if no swaps are made during one of the iterations of the outer loop (since that means the array is sorted).

Difference

In insertion sort elements are bubbled into the sorted section, while in bubble sort the maximums are bubbled out of the unsorted section.

7
  • 20
    Thanks, this is very clear! I think the main thing I needed highlighted is that the break statement in Insertion Sort means that it can terminate each iteration early: ie when it has found its position in the sorted section. Bubble sort requires that the swapping continues until the largest element in the unsorted section reaches the sorted section, so will never terminate early. It's a fantastic summary though, so +1
    – Migwell
    Commented Jun 24, 2013 at 9:42
  • 4
    I think that this should be the best answer :)
    – Adelin
    Commented Apr 29, 2014 at 21:08
  • 2
    Plus 1 for the clarity, the didactical value and for the main loop invariants of each the algorithm. It's a pity it doesn't contain explicitly the comparison of the complexity (expressed as a function of n), anyway I consider it a better answer than the accepted one, since from this I can see the difference. Commented Feb 22, 2015 at 14:01
  • Can I ask why do you swapping your item in your Insertation Pseudo code at every step? if(a[j-1] > a[j]) then a[j] = a[j-1] ELSE if(a[j-1] < e && a[j] >e) than a[j] = e;break; , where e is the item need to be sorted. With this solution, you not swapping already sorted items, just copying them. Looking forward to having you explanation, since I'm a bit confused.
    – narancs
    Commented Aug 23, 2016 at 21:14
  • @Karoly, I chose my version because it's simpler. Yours is slightly faster, it's good that you point it out. Wikipedia describes both version.
    – tom
    Commented Oct 2, 2016 at 6:13
48

In bubble sort in ith iteration you have n-i-1 inner iterations (n^2)/2 total, but in insertion sort you have maximum i iterations on i'th step, but i/2 on average, as you can stop inner loop earlier, after you found correct position for the current element. So you have (sum from 0 to n) / 2 which is (n^2) / 4 total;

That's why insertion sort is faster than bubble sort.

5
  • 2
    Algorithm explanation is on the web everywhere, I think. Commented Jun 24, 2013 at 8:39
  • 4
    yes, but it seems the OP still doesnt catch difference in the mechanisms
    – UmNyobe
    Commented Jun 24, 2013 at 8:40
  • 18
    Well you can sorta assume I understand the fundamentals. What I wanted was a comparison, and this is really quite good. So the idea is that while insertion sort causes the ith element to sink down, and bubble sort causes it to bubble up, insertion sort doesn't cause it to drop to the very bottom, it just causes it to drop into the right position in the already-sorted section. Thus it does less comparisons/swaps. Is that right?
    – Migwell
    Commented Jun 24, 2013 at 9:03
  • 2
    What? "So you have (sum from 0 to n) / 2 which is (n^2) / 4 total" That requires some expl, please! 0+1+2+3+4+5 = 15; 15/2=7.5; 7.5 * 4 = 30; sqrt(30)=gibberish
    – John Smith
    Commented Nov 24, 2019 at 13:17
  • @JohnSmith I believe there is a slight error in the answer. The sum from 1 to n is n*(n+1)/2 as it is a triangular number. Look up triangular number for more explanation. So that divided by 2 is just n*(n+1)/2. Commented Feb 7, 2020 at 12:15
16

Another difference, I didn't see here:

Bubble sort has 3 value assignments per swap: you have to build a temporary variable first to save the value you want to push forward(no.1), than you have to write the other swap-variable into the spot you just saved the value of(no.2) and then you have to write your temporary variable in the spot other spot(no.3). You have to do that for each spot - you want to go forward - to sort your variable to the correct spot.

With insertion sort you put your variable to sort in a temporary variable and then put all variables in front of that spot 1 spot backwards, as long as you reach the correct spot for your variable. That makes 1 value assignement per spot. In the end you write your temp-variable into the the spot.

That makes far less value assignements, too.

This isn't the strongest speed-benefit, but i think it can be mentioned.

I hope, I expressed myself understandable, if not, sorry, I'm not a nativ Britain

2
  • 1
    "and then put all variables in front of that spot 1 spot backwards" — and doesn't that also require a load of assignments, to shift the data? (assuming data is stored contiguously anyway, not a linked-list) Commented Dec 2, 2016 at 17:59
  • 1
    @MarkKCowan, yes, that's where insertion sort makes assignment per 'spot' as the above user put it. Basically, insertion sort can be written with one assignment in the inner loop, while bubblesort has 3 assignments in the inner loop.
    – JSQuareD
    Commented Jul 21, 2017 at 15:10
9

The main advantage of insert sort is that it's online algorithm. You don't have to have all the values at start. This could be useful, when dealing with data coming from network, or some sensor.

I have a feeling, that this would be faster than other conventional n log(n) algorithms. Because the complexity would be n*(n log(n)) e.g. reading/storing each value from stream (O(n)) and then sorting all the values (O(n log(n))) resulting in O(n^2 log(n))

On the contrary using Insert Sort needs O(n) for reading values from the stream and O(n) to put the value to the correct place, thus it's O(n^2) only. Other advantage is, that you don't need buffers for storing values, you sort them in the final destination.

4
  • If it's ok for an in-order traversal of the data to be something other than simply scanning an array, you can sort on the fly much more efficiently. e.g. insert elements into a binary tree as you receive them. This gives you O(n log(n)) total work performed to have a sorted collection at every step along the way. (An in-order traversal at any point is O(m)). If you just need a sorted result at the end, but want to overlap sorting computation with the transfer time of the data a Heap may be good. (And works in-place, like insertion-sort). Commented Jul 3, 2017 at 12:39
  • Anyway, neither bubble-sort nor insertion-sort are ideal for this with problem sizes large enough for O(f(n)) complexity class to matter more than implementation details and constant factors. Commented Jul 3, 2017 at 12:40
  • Correction: A heap isn't good for this. It does most of the sorting work as you remove elements in sorted order, which is why growing is so cheap. The goal here is to have most of the work done by the time the last element arrives. Commented Jul 3, 2017 at 12:49
  • Anyway, if you did need to maintain a sorted array for n insertions, then really it boils down to what algorithm is best for sorting an almost-sorted array where there's one un-sorted element at the top. Many O(n log(n)) sorting algorithms are O(n) in the almost-sorted case, so it's not true that you'd need sum(M=1..n, O(M * log(M)) ) work. That would indeed be O(n^2 log(n)), but with the right choice of algorithm they'll be O(n^2) total work. Insertion-sort is the most efficient for this, though. Commented Jul 3, 2017 at 12:57
7

Bubble Sort is not online (it cannot sort a stream of inputs without knowing how many items there will be) because it does not really keep track of a global maximum of the sorted elements. When an item is inserted you will need to start the bubbling from the very beginning

4

well bubble sort is better than insertion sort only when someone is looking for top k elements from a large list of number i.e. in bubble sort after k iterations you'll get top k elements. However after k iterations in insertion sort, it only assures that those k elements are sorted.

1

Though both the sorts are O(N^2).The hidden constants are much smaller in Insertion sort.Hidden constants refer to the actual number of primitive operations carried out.

When insertion sort has better running time?

  1. Array is nearly sorted-notice that insertion sort does fewer operations in this case, than bubble sort.
  2. Array is of relatively small size: insertion sort you move elements around, to put the current element.This is only better than bubble sort if the number of elements is few.

Notice that insertion sort is not always better than bubble sort.To get the best of both worlds, you can use insertion sort if array is of small size, and probably merge sort(or quicksort) for larger arrays.

1
  • 2
    If the number of elements are not small, how would bubble sort be better? My understanding is that whether you slide in IS or swap in BS would depend on whether the element compared is greater (IS) or smaller (BS) and not on the # of elements. Please correct me if wrong.
    – Asif
    Commented Mar 17, 2016 at 23:32
1

Number of swap in each iteration

  • Insertion-sort does at most 1 swap in each iteration.
  • Bubble-sort does 0 to n swaps in each iteration.

Accessing and changing sorted part

  • Insertion-sort accesses(and changes when needed) the sorted part to find the correct position of a number in consideration.
  • When optimized, Bubble-sort does not access what is already sorted.

Online or not

  • Insertion-sort is online. That means Insertion-sort takes one input at a time before it puts in appropriate position. It does not have to compare only adjacent-inputs.
  • Bubble-sort is not-online. It does not operate one input at a time. It handles a group of inputs(if not all) in each iteration. Bubble-sort only compare and swap adjacent-inputs in each iteration.
-1

insertion sort:

1.In the insertion sort swapping is not required.

2.the time complexity of insertion sort is Ω(n)for best case and O(n^2) worst case.

3.less complex as compared to bubble sort.

4.example: insert books in library, arrange cards.

bubble sort: 1.Swapping required in bubble sort.

2.the time complexity of bubble sort is Ω(n)for best case and O(n^2) worst case.

3.more complex as compared to insertion sort.

1
  • 1
    How come swapping is not required? It swaps elements to put an element into correct position. And I wouldn't say that bubble sort is more complex.
    – parsecer
    Commented Mar 5, 2020 at 8:23
-1

I will try to give a more concise and informative answer than others.

Yes, after each pass, insertion sort and bubble sort intuitively seem the same - they both build a sorted sublist at the edge.

However, insertion sort will perform fewer comparisons in general. With insertion sort, we are only performing a linear search in the sorted sublist with each pass. With random data, you can expect to make m/2 comparisons and swaps, where m is the size of the sorted sublist.

With bubble sort, we are always comparing EVERY pair in the unsorted sublist with each pass, so that's n-m comparisons (twice as many as insertion sort on random data). This means bubble sort is bad if comparisons are expensive/slow.

Also, the branching associated with swaps and compares for insertion sort is more predictable. We do a linear search at the same time as a linear insert, and we can generally predict/assume that the linear search/insert will continue until the correct space is found. With bubble sort, branching is essentially random, and we can expect a branch miss half the time! With every single compare! This means bubble sort is bad for pipelined processors if comparisons and swaps are relatively cheap/fast.

These factors make bubble sort much slower in general than insertion sort.

-1

Insertion Sort: We insert the elements into their proper positions in the array, one at a time. When we reach the nth element in the array, the n-1 elements are sorted.

Bubble Sort: We start with a bubble of one element and keep extending the bubble by a quantity of 1, until all elements are added. At any iteration, we simply swap the adjacent elements in the proper order so as to get the largest element at the end of the bubble. In this way, we keep on putting the largest element at the end of the array, and finally after all iterations our sorting is done.

Bubble Sort and Insertion sort complexity: O(n^2)

Insertion is faster as compared to Bubble sort, for the following reason:

Insertion sort just compares an element to a sorted array, that is ith element to the array containing 1...i-1 elements, which are sorted already. Therefore, there are less number of comparisons and swaps. In Bubble sort, however, as the bubble increases, the same iteration of comparing each pair of neighbors runs. This leads to a lot more comparisons and swapping as compared to Insertion Sort.

Therefore, even though the time complexity of both the algorithms is O(n^2); insertion sort results in a faster approach that bubble sort.

-1

Sorting algorithms can sometimes be challenging to grasp just by looking at the code. That's why visual explanations are valuable in helping us understand how these algorithms work.

One such example is the Insertion Sort algorithm. I recently came across a fantastic video https://www.youtube.com/watch?v=8mJ-OhcfpYg that provides a clear and visual explanation of the concept.

The video walks through the step-by-step process of Insertion Sort using animations and illustrations. It demonstrates how the algorithm iteratively builds the sorted portion of the array, one element at a time, by shifting elements and inserting them into the correct position.

By watching the video, you can gain a deeper understanding of the Insertion Sort algorithm and its inner workings. Visualizing the sorting process can make the code flow more naturally and help you grasp the underlying logic.

So, I highly recommend checking out the video https://www.youtube.com/watch?v=8mJ-OhcfpYg to enhance your understanding of Insertion Sort. It's a great resource that complements the algorithmic explanation and provides a visual perspective on how the sorting process unfolds."

-1

@sasha.sochka 's answer provides an excellent overview of the difference between the two.

But why is insertion sort preferred?

"Steven" on Quora has provided an insightful answer: https://qr.ae/psLRIf

"It depends on what you mean by partially sorted. Selection sort is always slow, but bubble sort may be fast in cases where a small number of passes over the array suffices.

If the ordering is like 912345678, then bubble sort will pass over the array once and leave it in sorted order, much faster than selection sort.

If the ordering is like 234567891, then bubble sort will only move the smallest value one position to the left per pass, so it will be as bad as selection sort.

So, bubble sort can be faster on partially sorted data, but not very reliably so. Insertion sort is a better option. It will be fast on both example orderings, and in general is robust at exploiting partial ordering in the input array."

-1

It's great that you're digging into how these sorting algorithms work! Though both Bubble and Insertion Sorts have the same time complexity, O(n²), in both the worst and average cases, they work differently. These differences explain why Insertion Sort is generally considered better.

How the Algorithms Work.

  1. Bubble Sort:

Mechanism: Bubble Sort works by stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The pass-throughs "bubble" the largest unsorted element to its correct position. Behavior: The algorithm of Bubble Sort performs element comparisons and potential swaps between the two adjacent elements in each pass. After each complete pass, the next largest element goes to its final position at the end of the array. It is done iteratively until the array is sorted.

Comparisons/Swaps: It consistently makes O(n) comparisons per pass whether the array is already sorted or nearly sorted. As a result, there are unwanted comparisons even when the array is nearly sorted.

  1. Insertion Sort:

Process: Insertion sort builds the sorted array one element at a time by taking an element from the unsorted portion of the list and placing it into its correct position within the sorted portion.

Behavior: Insertion sort picks the next element and places it in its correct position by shifting larger elements to the right. Starting with the first element as a "sorted" list of one, the sorted portion of the list grows one element at a time.

Comparisons/Swaps: The number of comparisons rises slowly as more elements are sorted. In case of the array nearly being sorted, Insertion sort performs fewer comparisons and swaps and hence is effective in this case.

Distinguishing Features of Their Operation Movement of Elements:

Bubble Sort: In every single pass of the array, the biggest element is moved to its correct position at the right. In this algorithm, the program keeps comparing and swapping till the entire list is sorted.

Insertion Sort: Places each element in its appropriate position within the sorted array it scans through. It makes fewer comparisons and swaps, especially for nearly sorted arrays.

Efficiency on Nearly Sorted Data:

Bubble Sort: Unless an optimization like early termination is applied to it, it will go on making O(n²) comparisons and swaps even if the array is nearly sorted. Insertion Sort: Intrinsically does well with nearly sorted data, since it has to make few comparisons to put every element in its rightful place and may attain almost O(n) in such cases.

Typical Use Case:

Bubble Sort: Rarely used in practice due to its inefficiency compared to other algorithms.

Insertion Sort: Practically, it is useful when the data is nearly sorted or small. Used in hybrid sorting algorithms like Timsort.

Why Quicksort is Generally Better Adaptability: Insertion sort does better for partially sorted arrays and, in general, it is more efficient in real-world use due to data often being nearly sorted.

Fewer Swaps: Insertion sort generally involves fewer swaps. It shifts only those elements that are necessary and does not swap the adjacent elements again and again. Thus, the overall cost of the operation is reduced.

Practical Performance: Insertion sort performs better and faster than bubble sort for small or nearly sorted datasets in practice even though it has the same time complexity as O(n²).

1
  • This looks like AI generated content.
    – karel
    Commented Sep 6 at 8:38
-2

Insertion sort can be resumed as "Look for the element which should be at first position(the minimum), make some space by shifting next elements, and put it at first position. Good. Now look at the element which should be at 2nd...." and so on...

Bubble sort operate differently which can be resumed as "As long as I find two adjacent elements which are in the wrong order, I swap them".

2
  • That does help with insertion sort, but your explanation of bubble sort doesn't include the actual loops so I can't really compare them. I insertion sort also effectively has the rule As long as I find two adjacent elements which are in the wrong order, I swap them, it's the way the loops operate that is different.
    – Migwell
    Commented Jun 24, 2013 at 8:55
  • 3
    Isn't that selection sort?
    – user555045
    Commented Jun 24, 2013 at 9:21
-2

Bubble Sort is repeatedly compares and swaps adjacent elements to "bubble" the largest to the end. It continues even if the array is nearly sorted, making it inefficient but Insertion Sort builds a sorted portion one element at a time by inserting each new element into its correct position. It's more efficient for small or nearly sorted arrays. that is the main diffrent of these 2 sorting algorithm.

I'm also think Insertion Sort Is Better than bubble sort because,

  1. Insertion sort adapts to nearly sorted data, making fewer comparisons and swaps.
  2. It typically performs fewer swaps, leading to better real-world performance.
  3. Both algorithms are O(n²), insertion sort generally runs faster in practice due to lower overhead.
  4. It avoids unnecessary operations, focusing only on placing each new element correctly.
-2

You're correct, In the observing that both Bubble Sort and Insertion Sort have a time complexity of 𝑂(𝑛2). However, there are key differences between the two that explain why Insertion Sort is generally considered better.

In Bubble Sort, each pass through the array compares adjacent elements and swaps them if they are in the wrong order. The largest unsorted element "bubbles up" to its correct position at the end of the array with each pass, but In the Insertion Sort, on the other hand, builds the sorted array one element at a time. It takes the next unsorted element and inserts it into its correct position within the sorted portion of the array, shifting elements as necessary.

Furthermore Bubble Sort typically performs more swaps because it repeatedly passes through the array and swaps elements even if they are only slightly out of order. Every adjacent comparison might lead to a swap, but Insertion Sort usually performs fewer swaps because it shifts elements in a more targeted way. It finds the correct position for the current element and moves the rest of the sorted elements in one go. Efficiency on Partially , Bubble Sort doesn't take advantage of partially sorted arrays as effectively as Insertion Sort. It will still perform unnecessary comparisons and swaps, butInsertion Sort is more efficient for nearly sorted arrays because it quickly identifies and places each element in its proper position with minimal movement.

In exploring both algorithms, Insertion Sort's approach is generally more efficient, especially on partially sorted arrays, leading to better overall performance in practice. This is overviwe why Insertion Sort is better than Bubble Sort.

-3

Bubble sort is almost useless under all circumstances. In use cases when insertion sort may have too many swaps, selection sort can be used because it guarantees less than N times of swap. Because selection sort is better than bubble sort, bubble sort has no use cases.

1
  • 1
    This is wrong, selection sort is in fact worse than bubble sort. Selection sort guarantees N^2 times of swap in both best case and worst case. Bubble sort at least has N times of swap in best case only matching bubble sort's time complexity in worst case.
    – douglas
    Commented Jun 12, 2022 at 3:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.