Is insertion sorting better than bubble sorting?

Question

I am doing my audit for the exam.

I would like to know under what conditions insert sorting will be better than bubble sorting, given the same average complexity of the O (N ^ 2) case.

I found some related articles, but I cannot understand them.

Could someone explain this in a simple way?

Answer 1

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

BubbleSort Best Case Scenario: O (n)

However, even in this case, the sorting of the insert became better / the same.

Bubblesort is more or less useful only for understanding and / or learning the sorting mechanism, but does not find the right use in programming these days, because its complexity

About (N²)

means that its effectiveness decreases sharply on lists of more than a small number of elements.

Answer 2

The following occurred to me:

• Sorting Bubble always takes another pass through the array to determine if it is sorted. On the other hand, insertion sorting is not needed - when inserting the last element, the algorithm guarantees array sorting.

• Bubble sorting makes n comparisons on each pass. Sorting an insertion makes less than n comparisons: as soon as the algorithm finds the position at which to insert the current element, it stops making comparisons and takes the next element.

• Finally, a quote from wikipedia :

The Bubble variety also interacts poorly with modern processor hardware. This requires at least twice as many records as sorting an insert, twice as many cache misses, and asymptotically more fictitious predictions. Astrachan's string sorting experiments in Java show bubble sorting is about 5 times slower than insert sorting, and 40% slower than sorting selection

Here you can find a link to the original research paper.

Answer 3

I think the answer you are looking for is here :

Bubble can also be used effectively in a list that is already sorted, with the exception of a small number of items. For example, if only one element is out of order, sorting the bubbles will take only 2 times. If the two elements are not in order, the sorting of the bubbles will take no more than 3 times ...

and

Sorting insert is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and is often used as part of more complex algorithms.

Answer 4

Could you provide links to related articles that you don’t understand? I'm not sure what aspects they can solve. In addition, there is a theoretical difference, which may be that bubble sorting is more suitable for collections represented as arrays (than those presented as linked lists), while insertion sorting is suitable for linked lists.

The reason may be that the sorting of bubbles always swaps two elements at the same time, which is trivial for both the array and the linked list (more efficiently on arrays), whereas insertion sorting inserts in the place in this list, which is trivial for related but includes moving all subsequent elements in the array to the right.

Having said that, take it with salt. First of all, sorting arrays in practice is almost always faster than sorting linked lists. Just because scanning a list once makes a huge difference. In addition, moving n elements of the array to the right is much faster than performing n (or even n / 2) swaps. This is why other answers correctly claim that insertion sorting is excellent overall and why I really think about the articles you read, because I cannot come up with an easy way to say that it is better in cases A, and it is better in cases B.