Why is insertion sort faster than quick-sort and bubble-sort for small cases?

Question

I recently read an article that talked about the computation complexity of algorithms. The author mentioned "why insertion sort is faster than quick-sort and bubble-sort for small cases". Could anybody make some explanation for that?

Does anybody know the actual complexity of each sort algorithm I mentioned above?

Did it say 'small cases' or something like 'almost-sorted cases' or 'few differences'? For small cases, a modified bubblesort is faster than insertion sort — Foo Bah, Oct 04 '11 at 04:42
@FooBah, I said small cases, which means case with small size. — antonio081014, Oct 04 '11 at 05:32
Then what you read is wrong. bubble sort is faster for small cases than insertion sort — Foo Bah, Oct 04 '11 at 05:48
@FooBah, do you have any further math support for your conclusion? I mean any math expression, or formula, please... — antonio081014, Oct 04 '11 at 05:51

score 3 · Accepted Answer · answered Oct 04 '11 at 04:47

3

Consider two complexity functions:

F(X) = X^2
G(X) = 4 * X * ln(X)

F(3) = 9
G(3) = 13

So algorithm F wins for 3 items. But:

F(100) = 10,000
G(100) = 1,842

So algorithm G wins for 100 items.

Insertion sort's complexity is like F(X). Quick sort's complexity is like G(X).

answered Oct 04 '11 at 04:47

David Schwartz

179,497
17
214
278

The worst case complexity of naïve QuickSort is O(N^2); the normal complexity is O(N log N). The complexity of both insertion sort and bubble sort is O(N^2). – Jonathan Leffler Oct 04 '11 at 05:41
Doesn't explain how insertion sort beats bubble sort. – Foo Bah Oct 04 '11 at 05:46
3

@Foo Bah: According to Sedgewick, on average Bubble sort uses N^2 / 2 comparisons and N^2 / 2 exchanges. Insertion sort uses N^2 / 4 comparisons and N^2 / 8 exchanges. Both are O(N^2), but the other factors make insertion sort faster. – rossum Oct 04 '11 at 11:27
@rossum I don't disagree with analysis for large N. However for small N the overhead and other effects actually support bubble sort. – Foo Bah Oct 04 '11 at 13:10

jamesatha · Answer 2 · 2011-10-04T06:00:34.953

0

If a list is already sorted, quicksort needs to go through all the recursive steps to get to n lists of size 1. Both of these take time. But the insertion sort will iterate though the list once and find out that it is done. This is the fastest for this case.

When the list is small, the overhead to make recursive calls and finding the pivot value, etc is much slower than the iterative process used in insertion sort.

edited Oct 04 '11 at 06:00

answered Oct 04 '11 at 05:18

jamesatha

7,280
14
37
54

1

bubble sort makes 1 pass for a sorted list. You stop the sort when the list is sorted. – Foo Bah Oct 04 '11 at 05:47
Foo Bah, good call. I was thinking about the wrong sort and have edited it – jamesatha Oct 04 '11 at 06:01

score 0 · Answer 3 · edited Dec 20 '11 at 12:06

0

Actual complexity of each sorting algorithm is as follows:

Best - Insertion Sort: O(N ^ 2), O(N), O(N ^ 2)
Average - Quick Qort: O(N ^ 2), O(N log N), O(N log N)
Worst - Bubble Sort: O(N ^ 2), O(N), O(N ^ 2)

edited Dec 20 '11 at 12:06

Cosmin

21,216
5
45
60

answered Oct 04 '11 at 05:46

Sitesh Shrivastava

29
2
12

Do you know the actual math expression for each of the average case? – antonio081014 Oct 04 '11 at 05:48
For Quick Sort it is T(n) = O(n) + 2T(n/2) For rest, if you have Cormen book with you, there is a thorough analysis of these algorithms. – Sitesh Shrivastava Oct 04 '11 at 06:01
@SITZ the rest of the world calls it CLR or CLRS – Foo Bah Oct 04 '11 at 06:05

Why is insertion sort faster than quick-sort and bubble-sort for small cases?

3 Answers3

Linked