Question

Consider the following array.

23

32

45

69

72

73

89

97

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above array in ascending order?
1. Insertion sort
2. Selection sort
3. Quicksort using the last element as pivot
4. Merge sort

Answer 1

Correct Answer - Option 1 : Insertion sort

Insertion sort:

In Insertion sort, the best-case takes Θ (n) time, the best case of insertion sort is when elements are sorted in ascending order. In that case, the number of comparisons will be n - 1 = 8 - 1 = 7

It is the least  number of comparisons (among the array elements) to sort the above array in ascending order:

The number of swaps needed is zero.

In Insertion sort, the worst-case takes Θ (n2) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.