Gate Questions on Sorting - Part 2

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(n² Logn)
2. O(n²)
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. Θ(n²)
4. Θ(n² 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. N²
3. NlogN
4. N(logN)²

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.