Skip to content
GATETECH
Official PYQ · 2015Set 2 · Q45Searching, Sorting, HashingMCQ1 mark

GATE CS 2015 Set 2 Q45 — Searching, Sorting, Hashing

Explain with AI

Suppose you are provided with the following function declaration in the C programming language.

int partition(int a[], int n);

The function treats the first element of a[ ]a[\:] as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part.

The following partially given function in the C programming language is used to find the kthk^{th} smallest element in an array a[ ]a[\:] of size nn using the partition function. We assume k≤nk \leq n.

int kth_smallest (int a[], int n, int k)
{
    int left_end = partition (a, n);
    if (left_end+1==k) {
        return a[left_end];
    }
    if (left_end+1 > k) {
        return kth_smallest (___________);
    } else {
        return kth_smallest (___________);   
    }
}

The missing arguments lists are respectively

Choose one option
View worked solution

Answer: A

The partition function divides the array of size nn into two parts around a pivot:

  • Left part: Contains elements ≤\le pivot. Its size is left_end.
  • Right part: Contains elements >> pivot. Its size is n−left_end−1n - \text{left\_end} - 1.

We are looking for the kthk^{\text{th}} smallest element:

  1. Case 1: left_end + 1 > k
    The kthk^{\text{th}} smallest element lies in the left part. We recursively search in the left subarray, which starts at address a, has size left_end, and we still look for the kthk^{\text{th}} smallest element.
    Thus, the call is: kth_smallest(a, left_end, k).
  2. Case 2: left_end + 1 < k
    The kthk^{\text{th}} smallest element lies in the right part. The right subarray starts at index left_end + 1 (address a + left_end + 1) and has size n - left_end - 1. Since we discard the first left_end + 1 elements, we now search for the (k−left_end−1)th(k - \text{left\_end} - 1)^{\text{th}} smallest element in this subarray.
    Thus, the call is: kth_smallest(a + left_end + 1, n - left_end - 1, k - left_end - 1).

Therefore, the correct option is A.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Searching, Sorting, Hashing questions