Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Gate Questions on Sorting
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

Gate Questions on Sorting: Part 1

Author Tanay Kumar
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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 Data Structures 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

Let us now discuss the previously asked gate questions on Sorting.

1. An array of 25 unique elements is to be sorted using the Quicksort. Assume that the pivot element is selected uniformly at random. The probability that the pivot element will get placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ______. [GATE CSE 2019]
 

Solution: 0.08

Worst case position in the pivot element is either first or last.
Since, Probability of placing pivot element in worst possible location= Favorable outcome / Total outcome  = 2/25 = 0.08.
 

2. Assume that the algorithms considered here will sort the input sequences in ascending order. If the input is already sorted, which of the following are TRUE? [GATE CSE 2016 Set 2]

  1. I and II only
  2. I and III only
  3. II and IV only
  4. I and IV only
     

Solution: (D) I and IV only

If the input is already sorted, the time complexity will be like this:

I. Quicksort will run in O(n2)
II. Bubble sort will run in O(n) time
III. Merge sort will run in O(n log n) time
IV. Insertion sort will run in O(n) time
 

3. The worst-case running times of Insertion sort, Merge sort, and Quicksort, respectively, are: [GATE CSE 2016 Set 1]

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

Solution: (D)
Worst-case running time of insertion sort:  Θ(n2)
Worst-case running time of merge sort: Θ(n logn)
Worst-case running time of quick sort: Θ(n2)
 

4. Consider the following array { 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 }. The minimum number of swap operations needed to convert it into a max-heap is [GATE CSE 2015 Set 3]

  1. 4
  2. 5
  3. 2
  4. 3
     

Solution: (D)

The minimum number of swap operations needed to convert the above tree to a Max heap is 3. Below are three swap operations.
Swap 100 with 15
Swap 100 with 50
Swap 100 with 89


5. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is [GATE CSE 2015 Set 2]

  1. Θ(nlogn)
  2. Θ(n)
  3. Θ(logn)
  4. Θ(1)
     

Solution: (D)

We need to consider only three elements and compare them. Hence the number of comparisons is constant, making the time complexity as Θ(1).


6. Which one of the following is the recurrence equation for the worst-case time complexity of the Quicksort algorithm for sorting n( ≥ 2 ) numbers? In the recurrence equations given in the options below, c is a constant. [GATE CSE 2015 Set 1]

  1. T(n) = 2T (n/2) + cn
  2. T(n) = T(n – 1) + T(0) + cn
  3. T(n) = 2T (n – 2) + cn
  4. T(n) = T(n/2) + cn
     

Solution: (B)
In the worst case, the chosen pivot is always placed at a corner position and the recursive call is made for the following.
a) for subarray on the left of the pivot, which is of size n-1 in the worst case.
b) for subarray on the right of the pivot, which is of size 0 in the worst case.
 

7. What is the number of swaps required to sort n elements using selection sort in the worst case? [GATE CSE 2009]

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

Solution: (A)
Selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort.


8. Which of the following sorting algorithms has the lowest worst-case complexity? [GATE CSE 2007]

  1. Merge sort
  2. Bubble Sort
  3. Quick Sort
  4. Selection Sort
     

Solution: (A)

Worst case complexities for the above sorting algorithms are as follows:
Merge Sort — Θ(n logn)
Bubble Sort — Θ(n2)
Quick Sort — Θ(n2)
Selection Sort — Θ(n2)
 

9. Which one of the following in place sorting algorithms needs the minimum number of swaps? [GATE CSE 2006]

  1. Insertion Sort
  2. Quick Sort
  3. Heap Sort
  4. Selection Sort
     

Solution: (D)
Selection Sort is the algorithm requiring a minimum number of swaps for sorting. It works on the greedy approach and requires O(n) swaps to sort the array of n elements.


10. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

  1. N
  2. N2
  3. NlogN
  4. N(logN)2
     

Solution: (C)

The number of comparisons that the comparison sort algorithm takes increases in proportion to N log(N), where N is the total number of elements to sort.


11. Suppose we want to arrange the n numbers stored in an array such that all negative values occur before all positive ones. The minimum number of exchanges required in the worst case is [GATE CSE 1999]

  1. n - 1
  2. n
  3. n + 1
  4. None of the above


Solution: (D)
The worst case happens if all the positive numbers occur before all the negative numbers.

In this case, take any positive number from the left and a negative number from the right and do a swap operation. Then after n/2 swaps, we will reach the middle of the array, and all the negative values will be present before the positive value.

So in the worst-case n/2 exchanges are required.

 

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

Refer to know about :  Topological sort

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. What are the types of sorting in data structure?
    There are various types of sorting in data structures: insertion sort, bubble sort, merge sort, quick sort, selection sort, bucket sort, radix sort, heap sort, etc.
     
  2. The most efficient sorting algorithm would be?
    Quicksort is one of the most efficient sorting algorithms, and this makes it one of the most used as well. Its best and average time complexity is O(n logn).
     
  3. What is the principle of merge sort?
    Merge sort is an efficient sorting algorithm. It works on the principle of the divide and conquers algorithm. Merge sort repeatedly breaks down an array into several subarrays until each subarray consists of a single element and merges those subarrays in a manner that results in a 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.

Recommended Problems - 


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 Sorting Based ProblemsQueue Gate Questions, Linked list Gate QuestionsArray Gate QuestionsOnline Mock Test Series. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Gate Questions on Searching: Part 2
Next article
Gate Questions on Sorting - Part 2
Live masterclass