October 15, 2023
October 15, 2023
October 15, 2023
###### NIC-NIELIT STA 2020
October 15, 2023
 Question 21
Consider the following array. 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 Quicksort using the last element as pivot B Insertion sort C Selection sort D Mergesort
Question 21 Explanation:

Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).

Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity.

Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum.

Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.

The number of comparisons will not take more than “n” for the given input array.

Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity.

Question 21 Explanation:

Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).

Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity.

Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum.

Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.

The number of comparisons will not take more than “n” for the given input array.

Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity.