Insertion sort better than Bubble sort?

algorithm sorting bubble-sort insertion-sort
Jonathan picture Jonathan · May 3, 2012 · Viewed 23.4k times · Source

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?

Answer

Ben Win picture Ben Win · May 3, 2012

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.

Related questions

Bubble Sort Homework

In class we are doing sorting algorithms and, although I understand them fine when talking about them and writing pseudocode, I am having problems writing actual code for them. This is my attempt in Python: mylist = [12, 5, 13, 8, 9, 65] def bubble(badList): length = …

Read More
What is a bubble sort good for?

Do bubble sorts have any real world use? Every time I see one mentioned, it's always either: A sorting algorithm to learn with. An example of a sorting algorithm not to use.

Read More
Why is bubble sort O(n^2)?

for (int front = 1; front < intArray.length; front++) { for (int i = 0; i < intArray.length - front; i++) { if (intArray[i] > intArray[i + 1]) { int temp = intArray[i]; intArray[i] = intArray[i + 1]; intArray[i + 1] = temp; } } } The inner loop is iterating: …

Read More