Table of contents
1.
Introduction
2.
Gate Questions on Sorting
3.
FAQs
4.
Conclusion
Last Updated: Mar 27, 2024

Gate questions on Sorting - Part 3

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

As we all know, sorting is one of the most powerful and frequently used algorithms in programming languages. We can use the Sorting algorithm to rearrange a given list or array of elements according to the comparison operator on the elements. 

Refer to Sorting in Data Structure: Categories & Types for more detail on the topic.

This article will discuss previous years' gate questions on sorting with proper solutions and explanations.

Gate Questions on Sorting

1. In quick sort, for sorting n elements, we choose the n/4th smallest element as a pivot with an O(n) time algorithm. What is the worst-case time complexity for the quick sort? [GATE CS 2009]

  1. Θ(n)
  2. Θ(n log n)
  3. Θ(n2)
  4. Θ(n2 log n)
     

Solution: (B)

The recursion expression for the given condition becomes: T(n) = T(n/4) + T(3n/4) + c*n. After solving this recursion, we get Θ(n Logn).


2. Assume the Quicksort algorithm. Suppose we have a procedure for finding the pivot element that splits the set into two subsets, each containing at least 1/5th of the elements. Let T(n) be the number of comparison operations required to sort n elements. Then [GATE CS 2008]

  1. T(n) <= 2T(n/5) + n.
  2. T(n) <= T(n/5) + T(4n/5) + n.
  3. T(n) <= 2T(4n/5) + n.
  4. T(n) <= 2T(n/2) + n.


Solution: (B)
For this case where n/5 elements are in the same subset, we require T(n/5) comparisons for the first subset, T(4n/5) for the remaining 4n/5 elements, and we require n operations to find pivot. Also, if we have more than n/5 elements in the same set, the remaining elements will be less than 4n/5, and time complexity will become less than T(n/5) + T(4n/5) + n as the recursion tree will be more balanced.


3. Let P be a QuickSort algorithm program to sort numbers in ascending with the first element as a pivot. Let t1 & t2 be the number of comparison operations made by P for the inputs {1, 2, 3, 4, 5} & {4, 1, 5, 3, 2} respectively. Which of the following holds? [GATE CSE 2014 - SET 1]

  1. t1 = 5
  2. t1 < t2
  3. t1 > t2
  4. t1 = t2


Solution: (C)
When the first or last element is selected as the pivot, QuickSort's worst case occurs for the already sorted arrays. In every step of quicksort, numbers are divided as the following recurrence: T(n) = T(n-1) + O(n).
Average time complexity: t2 = O(logn)
Worst time complexity: t1 = O(n2).
Hence, t1>t2.


4. We have an array of sizes n. Suppose we implement quicksort by always selecting the middle element as the pivot. Then the tightest upper bound for the worst-case performance is [GATE-CS-2014-(Set-3)]

  1. O(n2)
  2. O(n Logn)
  3. Θ(n Logn)
  4. O(n3)


Solution: (A)
There are permutations for which the worst-case will be O(n2) for any input. In a few cases, choosing the central element minimizes the chances of getting O(n2), but it can reach O(n2) in the worst case. Whatever element we take as a pivot, either middle or first, the worst case will be O(n2as the pivot is fixed in position.


5. In a permutation a1, a2, a3,.... an of n unique integers, an inversion is a pair (ki, KJ) such that i < j and ki > KJ. What will be the worst-case time complexity for the Insertion Sort if the inputs are limited to permutations of 1.....n with at most n inversions? [GATE-CS-2003]

  1. Θ (n2)
  2. Θ (n log n)
  3. Θ (n1.5)
  4. Θ (n)


Solution: (D)
Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversions initially present in the array being sorted. 


6. Randomized quicksort algorithm is an extension of a quicksort algorithm where the pivot is selected randomly. What is the worst-case complexity of sorting n numbers with randomized quicksort? [GATE-CS-2001]

  1. O(n)
  2. O(n log n)
  3. O(n2)
  4. O(n!)


Solution: (C)
If all array elements are the same, that is the worst case for the randomized quicksort. The time complexity for the worst-case quicksort is O(n²), which is already proven. So, option (C) is correct.


7. Which is the best sorting algorithm to use if the elements in the array are more than 1 million in general? [GATE CSE 2009]

  1. Merge sort.
  2. Bubble sort.
  3. Quicksort.
  4. Insertion sort.


Solution: (C)
The most practical implementation of QuickSort uses a randomized quicksort version. It has an expected time complexity of O(n Logn). The worst-case is possible in the randomized version, but the worst-case doesn't occur for any particular pattern (like a sorted array), and randomized Quick Sort works well in practice.


8. A sorting technique is called stable if: [GATE CSE- 1999]

  1. It takes O(n log n) time.
  2. It maintains the relative order of occurrence of the same elements.
  3. It uses a divide and conquer approach.
  4. It takes O(n) space.
     

Solution: (B)
A sorting technique is stable if two objects with the same keys appear in the same order in sorted output as they appeared in the input array. It means that two identical elements do not change the order in the process of sorting. Examples of such sorting methods are: Insertion sort, Merge Sort, Bubble Sort, etc.


9. Which of the below-given sorting techniques has the highest best-case runtime complexity. [GATE CSE 2017 mock]

  1. Quicksort
  2. Selection sort
  3. Insertion sort
  4. Bubble sort


Solution: (B)

The best time complexity for different sorting methods is as follows:
Quicksort – Ο(n logn)
Selection sort – Ο(n^2 )
Insertion sort – Ο(n)
Bubble sort – Ο(n)


10. If we use the RadixSort algorithm to sort n integers in the range [nk/2,nk], for any k>0 independent of n, the time taken will be? [GATE IT - 2008]

  1. Θ(n)
  2. Θ(k*n)
  3. Θ(n logn)
  4. Θ(n2)


Solution: (C)

Time complexity for radixsort = O(w*n)
for n keys of word size = w

Also, w = log(nk)
O(w*n)=O(k logn*n)
=> k O(n logn)
 

Refer to Gate Questions on Sorting: Part 1 and Gate Questions on Sorting: Part 2 for more questions. Also, check out the Gate Syllabus for CSE.

FAQs

  1. What is sorting with an example?
    Sorting is a method to put disarranged elements in either descending or ascending order. For example – [3,2,0,7, 8,11] the elements in this array are not arranged. After sorting the data in ascending order, it becomes – [0,2,3,7,8,11].
     
  2. What are the types of sorting in data structure?
    There are various sorting techniques, some of which are – bubble sort, quick sort, selection sort, insertion sort, merge sort, bucket sort, radix sort, heap sort, etc.
     
  3. What is quicksort?
    QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. After that, partition or rearrange the array into two sub-arrays such that each element in the left sub-array is less than or equal to the pivot element and each element in the right sub-array is larger than the pivot element. Repeat this process recursively and combine the already sorted array.
     
  4. What is the weightage of sorting questions in the gate exam?
    A total of 15 Questions are asked from the sorting topic of algorithms subject in previous gate papers. The average mark is 1.60.

Conclusion

In this article, we have extensively discussed previous years’ gate questions on sorting.

We hope that this blog has helped you enhance your knowledge on previous years’ gate questions on sorting, and if you would like to learn more, check out our articles on Queue Gate Questions, Linked list Gate Questions, and Array Gate Questions. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass