Insertion sort vs Bubble Sort Algorithms

AlgorithmSorting

Algorithm Problem Overview


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.

Algorithm Solutions


Solution 1 - Algorithm

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.

Solution 2 - Algorithm

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.

Solution 3 - Algorithm

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

Solution 4 - Algorithm

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.

Solution 5 - Algorithm

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

Solution 6 - Algorithm

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.

Solution 7 - Algorithm

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.

Solution 8 - Algorithm

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.

Solution 9 - Algorithm

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.

Solution 10 - Algorithm

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.

Solution 11 - Algorithm

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.

Solution 12 - Algorithm

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".

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionMigwellView Question on Stackoverflow
Solution 1 - AlgorithmtomView Answer on Stackoverflow
Solution 2 - Algorithmsasha.sochkaView Answer on Stackoverflow
Solution 3 - Algorithmuser5269260View Answer on Stackoverflow
Solution 4 - AlgorithmjnovachoView Answer on Stackoverflow
Solution 5 - AlgorithmJoe TamView Answer on Stackoverflow
Solution 6 - AlgorithmRajat PaliwalView Answer on Stackoverflow
Solution 7 - AlgorithmAravindView Answer on Stackoverflow
Solution 8 - AlgorithmKRoyView Answer on Stackoverflow
Solution 9 - AlgorithmDChenView Answer on Stackoverflow
Solution 10 - Algorithmabhishek agrawalView Answer on Stackoverflow
Solution 11 - AlgorithmndavidowView Answer on Stackoverflow
Solution 12 - AlgorithmUmNyobeView Answer on Stackoverflow