Sorting

Question

Which of the following sorting techniques have minimum number of comparision in best case?

1. Insertion Sort

2. Selection Sort

3. Merge Sort

4. Heap Sort

5.Quick Sort

 

The answer is insertion sort but my doubt is in insertion sort algo. inside the for loop the while loop condition is:-

while(i >= 0 && A[i] > Key){.....}

Now if say array is sorted in increasing order the while loop wont execute at all because the number of time while loop executes here = no. of inversions which is Zero in sorted array.But the comparison will be done for all the cases right. Then how come insertion sort possess O(n) number of comparisons in best case.Wont it have O(n^2) Comparisons.Becasue comparisons will be done in all the cases weather its sorted or not.

Comments

sorry there would be swap instead of comparison in my comment.

---

It's swapping that contributes to the time complexity, not comparison.

---

nice explanation, thanks!

Answer 1

As you can see when while loop condition becomes false, the control goes to outer for loop where j is incrementing again and key is set to A[j] and i=j-1 and A[i] will be compared to key again which will take O(1) time(just one comparision).This comparision will continue upto n times until outer for loop exits so in best case also n*O(1) which is O(n) time.

In worst case inner while loop comparision will take O(n) time so total time n*O(n) = O(n^2).

Comments

Ok my mistake i didnt looked correctly got it.