10

I am doing my revision for the exam.

Would like to know under what condition will Insertion sort performs better than bubble sort given same average case complexity of O(N^2).

I did found some related articles, but I can't understand them.

Would anyone mind explaining it in a simple way?

Jacob Schoen
  • 14,034
  • 15
  • 82
  • 102
Jonathan
  • 111
  • 1
  • 1
  • 3

5 Answers5

5

The advantage of bubblesort is in the speed of detecting an already sorted list:

BubbleSort Best Case Scenario: O(n)

However, even in this case insertion sort got better/same performance.

Bubblesort is, more or less, only good for understanding and/or teaching the mechanism of sortalgorithm, but wont find a proper usage in programming these days, because its complexity

O(n²)

means that its efficiency decreases dramatically on lists of more than a small number of elements.

Ben Win
  • 830
  • 8
  • 21
  • 3
    "bubblesort is only good for understanding and/or teaching the mechanism of sort algorithm" - not even that, I'd say. Insertion sort isn't any harder to understand and not much harder to code. Bubble sort has one very specific advantage, which is that it's provably the most efficient sort for a particular type of storage that doesn't have random access. Drum storage, I think, where the drum rotates at constant speed in one direction only. Then it beats insertion sort because insertion sort needs to "look backwards", which is very slow. This advantage is rarely of practical use these days! – Steve Jessop May 03 '12 at 10:17
4

Following things came to my mind:

  1. Bubble sort always takes one more pass over array to determine if it's sorted. On the other hand, insertion sort not need this -- once last element inserted, algorithm guarantees that array is sorted.

  2. Bubble sort does n comparisons on every pass. Insertion sort does less than n comparisons: once the algorithm finds the position where to insert current element it stops making comparisons and takes next element.

  3. Finally, quote from wikipedia article:

Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions. Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than selection sort

You can find link to original research paper there.

Asad-ullah Khan
  • 1,573
  • 18
  • 22
Victor Sorokin
  • 11,878
  • 2
  • 35
  • 51
  • thanks Victor. I found the first 2 points really useful. I understand now one fundamental difference between the 2 algorithms is the number of comparisons required. Cheers – Jonathan May 03 '12 at 10:46
  • 2nd point seems to be not correct. Yes some algorithms does that. But I think in the correct bubble sort algorithm, the inner loop runs n-1, n-2, n-3 .... times on each iteration of the outer loop. – Maduranga Siriwardena Jul 16 '14 at 17:08
0

I guess the answer you're looking for is here:

Bubble sort may also be efficiently used on a list that is already sorted except for a very small number of elements. For example, if only one element is not in order, bubble sort will take only 2n time. If two elements are not in order, bubble sort will take only at most 3n time...

and

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and often is used as part of more sophisticated algorithms

MarcoS
  • 13,386
  • 7
  • 42
  • 63
  • so for example a mostly sorted list: e.g. [ 2,3,4,5,1] bubble sort need 4 swaps and 4 comparisons Insertion sort need 4 swaps and 4 comparisons as well. so what is the difference? – Jonathan May 03 '12 at 09:44
  • in that particular example there's no difference :) – MarcoS May 03 '12 at 09:45
0

Could you provide links to the related articles you don't understand? I'm not sure what aspects they might be addressing. Other than that, there is a theoretical difference which might be that bubble sort is more suited for collections represented as arrays (than it is for those represented as linked lists), while insertion sort is suited for linked lists.

The reasoning would be that bubble sort always swaps two items at a time which is trivial on both, array and linked list (more efficient on arrays), while insertion sort inserts at a place in a given list which is trivial for linked lists but involves moving all subsequent elements in an array to the right.

That being said, take it with a grain of salt. First of all, sorting arrays is, in practice, almost always faster than sorting linked lists. Simply due to the fact that scanning the list once has an enormous difference already. Apart from that, moving n elements of an array to the right, is much faster than performing n (or even n/2) swaps. This is why other answers correctly claim insertion sort to be superior in general, and why I really wonder about the articles you read, because I fail to think of a simple way of saying this is better in cases A, and that is better in cases B.

b.buchhold
  • 3,837
  • 2
  • 24
  • 33
  • Bubble sort may be more suited to arrays than bubble sort is to linked lists, but bubble sort is not more suited to arrays than insertion sort is to arrays. – Steve Jessop May 03 '12 at 10:43
  • Yes, maybe I wasn't clear enough in the last paragraph. The thing is, bubble sort is conceptually trivial on arrays while insertion sort isn't ("move everything from x to right right"). Still it is true, that this doesn't make bubble sort faster. – b.buchhold May 03 '12 at 10:53
0

In the worst case both tend to perform at O(n^2)

In the best case scenario, i.e., when the array is already sorted, Bubble sort can perform at O(n).

Vineeth Chitteti
  • 1,454
  • 2
  • 14
  • 30
  • 1
    Bubble sort can be optimized to run in O(n) running time for best case. – Maduranga Siriwardena Jul 16 '14 at 17:03
  • Both bubble and insertion has the same complexity for worst/average/best case performances which is O(n^2) and also space complexity is both O(n) for them. – Levent Divilioglu Mar 03 '16 at 23:22
  • 1
    @LeventDivilioglu In the best case scenario Bubble Sort can perform at O(n). We can modify bubble sort in such a fashion that if no swaps happen during the first iteration, then we can stop checks as because the list is already sorted. – Vineeth Chitteti Nov 22 '18 at 15:10