Consider the following array: 23, 32, 45, 69, 72, 73, 89, 97.Which algorithm out of the following op

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2021 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2021 question covers Sorting topic.

Q: What is the difficulty level of this question?

This GATE-CS 2021 Algorithm question has a easy difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

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?

Accepted Answer

Correct Answer: (A) Insertion sortConcept -- Sorting Algorithm Comparisons on Already-Sorted Input:The array 23, 32, 45, 69, 72, 73, 89, 97 is already sorted in ascending order (n = 8 elements). This is the best case for insertion sort.Insertion sort (best case -- already sorted): For each element at position i (i = 2 to 8), it is compared with the element at position i-1 and found to be already in place, requiring exactly 1 comparison each. Total comparisons = n - 1 = 7.Selection sort (always O(n2)): Selection sort always scans the remaining unsorted portion to find the minimum, regardless of the initial order. Total comparisons = n(n-1)/2 = 8 &times; 7 / 2 = 28 comparisons.Merge sort (O(n log n)): Merge sort always divides and merges regardless of input order. For n=8: it performs approximately n log2n = 8 &times; 3 = 24 comparisons (actual count may vary between 17 and 24 depending on merge steps).Quick sort with last element as pivot on already-sorted array (worst case O(n2)): When the array is already sorted and the pivot is always the last element, each partition step produces one empty subarray and one subarray of size n-1. This results in n(n-1)/2 = 28 comparisons -- the absolute worst case for quicksort.Conclusion: Insertion sort with 7 comparisons uses the fewest comparisons on an already-sorted array of 8 elements.

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?

Master GATE-CS with Our Test Series

More Questions from Sorting

Frequently Asked Questions

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?

Master GATE-CS with Our Test Series

More Questions from Sorting

Frequently Asked Questions