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 2

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

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

1. Consider the following array {23, 32, 45, 69, 72, 73, 89, 97}. Which algorithm out of the given options uses the least number of comparisons ( among the elements ) to sort the above array in ascending order? [GATE CSE 2021 Set 1]

  1. Selection sort
  2. Mergesort
  3. Insertion sort
  4. Quicksort with the last element as a pivot
     

Solution: (C)

Since the given array is in ascending order, Insertion sort will provide its best case with the time complexity of order O(n).
 

2. Assume that the mergesort algorithm, in the worst case, takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size that solves it in 6 minutes? [GATE CSE 2015 Set 3]

  1. 256
  2. 512
  3. 1024
  4. 2048
     

Solution: (B)

The time complexity for merge sort is Θ(n Logn)
=> c*64Log64 = 30
=> c*64*6 = 30
=> c = 5/64

For time 6 minutes
5/64*nLogn = 6*60
nLogn = 72*64 = 512 * 9
Hence, n = 512.

Must Read Algorithm Types
 

3. Suppose we have an O(n) time algorithm that finds the median of the unsorted array. Now consider the QuickSort implementation where we first see the median using the above algorithm, then use the median as the pivot. What will be the worst-case time complexity of this modified QuickSort?

  1. O(n2 Logn)
  2. O(n2)
  3. O(n Logn * Logn)
  4. O(n Logn)
     

Solution: (D)

If we use median as the pivot element, then the recurrence for all becomes T(n) = 2T( n/2 ) + O(n). We can solve the above recurrence with the Master Method.


4. Which of the below-sorting algorithms in its typical implementation gives the best performance when applied on an array that is sorted or almost sorted (maximum 1 or 2 elements are misplaced)?

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


Solution: (A)

Insertion sort needs linear time when the input array is sorted or almost sorted (max 1 or 2 elements are displaced). Other Sorting algorithms listed above will take more than linear time in their typical implementation.


5. Given an unsorted array. In the array, every element in the array is at most k distance from its position in a sorted array where k is a positive integer smaller than the size of the array. Which sorting algorithm can we easily modify for sorting this array, and what is the available time complexity?

  1. Insertion sort with time complexity O(k n)
  2. Heap sort with time complexity O(n Logk)
  3. Quicksort with time complexity O(k Logk)
  4. Merge sort with time complexity O(k Logk)


Solution: (B)

1.) to sort the array, firstly, we will create a min-heap with the first k + 1 elements and separate array as the resultant array.
2.) because elements are at-most k distance apart from the original position, it is guaranteed that the minimum element will be in this K+1 element
3.) remove the minimum element from the min-heap and add it to the result array.
4.) Insert another element from the array into the min-heap; now, the second minimum element will be in this, then perform extract min, and continue this process until no more elements are in the unsorted array. finally, use a simple heap sort for the remaining elements

Time Complexity
1) O(k) to build the initial min-heap.
2) O((n - k) logk) for remaining elements.
3) 0(1) to extract min.

So total O(k) + O((n-k)logk) + 0(1) = O(nlogk)


6. Consider a situation where swapping operation is very costly. Which of the given sorting algorithms should be preferred so that the number of swap operations is minimum in general?

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


Solution: (B)

Selection sort takes O(n) swaps, the minimum among all given sorting algorithms above.


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 executed in selection sort.


8. Suppose we need to sort an array of eight integers using the quicksort algorithm, and we just finished the partitioning with the array: {2, 5, 1, 7, 9, 12, 11, 10}?

  1. The pivot could be either the seven or the 9.
  2. The pivot could be the 7, and it is not the 9.
  3. The pivot is not the 7, and it could be the 9.
  4. Neither the seven nor the 9 is the pivot.


Solution: (A)

7 and 9 are at their correct positions (as in a sorted array). Also, all elements on the left of 7 & 9 are smaller than 7 & 9, respectively and on the right are greater than 7 & 9, respectively.


9. Suppose we sort an array of eight integers using heapsort, and we have just finished some heapify (either minheapify or maxheapify) operations. The array looks like this: {16 14 15 10 12 27 28} How many heapify operations have been performed on the root of the heap?

  1. 1
  2. 2
  3. 3 or 4
  4. 5 or 6


Solution: (B)

In heapsort, we first build the heap and then do the following operations until heap size becomes 1. a.) Swap the root with the last element b.) Call the heapify for root c.) reduce the heap size by 1. In the question, it is mentioned that heapify is called a few times, and we see that the last two elements in the given array are the two largest elements in the array. So, the situation is clear that maxheapify is called two times.


10. What is the best time complexity for bubble sort?

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


Solution: (A)

O(n) is the best case when the array is in ascending order.


11. We have to sort 1 GB of data with only 100 MB of available memory. Which sorting technique will be most appropriate?

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


Solution: (B)

We can sort the data with external sorting, which uses the merging technique. We can do it as follows: 1.) Divide the data into ten groups, each of size hundred. 2.) Sort each group and write them to the disk. 3.) Load ten items from each group into the main memory. 4.) Output the minimum item from the main memory to the disk. Load the next item whose item was chosen. 5.) Loop step no. 4 until all items are not outputted. Step 3-5 is called as merging technique.


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

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 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. Explain the bubble sort algorithm?
    Bubble Sort is one of the simplest sorting algorithms that work by continuously swapping the adjacent elements of the list if they are in the wrong order.
     
  4. Which sort is the fastest?
    Quicksort is considered one of the fastest sorting algorithms. We can also view it as the best sorting algorithm. Some of its features are that it is a comparison sort and can be done in place in an array. However, an inefficient implementation it’s not a stable sort. Though the worst-case complexity is O(n2), on average, it gives us O(n logn) time complexity.

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 of 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 Sorting: Part 1
Next article
Gate questions on Sorting - Part 3
Live masterclass