MadeEasy Subject Test: Algorithms - Sorting

Question

Consider the following statements:
S1  : On any random input insertion sort is work more efficiently than bubble sort.
S2  : Average number of comparison of insertion sort is better than bubble sort by constant factor.
If efficiency, is considered as number of comparison to sort an array [input], then which of the above statement is correct?

Comments

S1 is false as it will not hold true when that random input turn outs to be in descending order.Which is basically the worst case of insertion sort comparisons O(n^2).Bubble sort will also have same number of comparison in this case.

---

insertion sort is best in comparison to bubble sort. Because in the best case or worst case in bubble sort, there is the same number of comparison while in insertion sort there is only n comparison in the best case and (n-square) in the worst case.

---

Both should be true.

Even in the worst case, when the input s sorted in reverse order. Bubble sort we need n(n-1)/2 comparisons and insertion sort will also take n(n-1)/2 comparisons.

And when the input is already sorted. Both will take only (n-1) comparisons.

But in other cases, insertion sort will require less number of comparisons.

Answer 1

S1 is false because for sorting in opposite order will take lot comparison compare to bubble sort.

S2 bubble sort has avrage n-1, n-2, n-3, --------1 comparison total aprox O((n-1)(n)+n-1)/4 and total O((n^2+n)/4) in insertion sort. show it's true.

Comments

for descending bubble sort  will also take 0 n^2  time

what if all ascending elements come in as input

then insertion performs better

so insertion is more efficient

---

if the given input is in descending order then insertion sort and bubble sort take same time O(n2).  If the input in ascending order then insertion sort takes O(n) and bubble sort O(n2).

So, I think the first one is true