Gate Questions on Sorting: Part 1

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(n²)
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 Θ(n²).
2. Θ(n²), Θ(n²), and Θ(n log n).
3. Θ(n²), Θ(n log n), and Θ(n log n).
4. Θ(n²), Θ(n log n), and Θ(n²).
    

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

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. Θ(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 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 — Θ(n²)
Quick Sort — Θ(n²)
Selection Sort — Θ(n²)
 

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. N²
3. NlogN
4. N(logN)²
    

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