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 the above array in ascending order?

• A. Selection sort
• B. Mergesort
• C. Insertion sort
• D. Quicksort using the last element as pivot

Hint:

Insertion sort is highly efficient for nearly sorted or fully sorted arrays due to its linear-time best case.

Answer 1

The Correct Option is C

Step 1: Observe the given array.
The given array is already sorted in ascending order.

Step 2: Analyze Insertion Sort.
Insertion sort performs best when the array is already sorted. In this case, each element is compared once with its predecessor, resulting in only \( n - 1 \) comparisons for an array of size \( n \).

Step 3: Compare with other algorithms.
Selection sort always performs \( \frac{n(n-1)}{2} \) comparisons regardless of input order.
Mergesort performs \( \Theta(n \log n) \) comparisons.
Quicksort using the last element as pivot on a sorted array leads to the worst-case behavior with \( \Theta(n^2) \) comparisons.

Step 4: Conclusion.
Insertion sort uses the least number of comparisons for an already sorted array.