GATE CS 2015 Set 2 Q.55 (CS Q.45): Searching and Sorting Algorithms

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[] 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 $k^{\text{th}}$ smallest element in an array a[] of size $n$ using the partition function. We assume $k \le 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 argument lists are respectively

(a, left_end, k) and (a+left_end+1, n-left_end-1, k-left_end-1)

(a, left_end, k) and (a, n-left_end-1, k-left_end-1)

(a+left_end+1, n-left_end-1, k-left_end-1) and (a, left_end, k)

(a, n-left_end-1, k-left_end-1) and (a, left_end, k)

Official answer and solution

Official answer: A
From: Official GATE 2015 answer key

Solution

Trace the recursive Quickselect arguments based on the rank of the pivot.

The function partition(a, n) places the pivot at the last element of the left subarray. The return value left_end is the number of elements in the left part.

Since left_end elements are $\le$ pivot, the pivot is at index left_end - 1 (or 1-based rank left_end). In the code:

If left_end + 1 == k, the target element is at index left_end.
If left_end + 1 > k, the $k^{\text{th}}$ $k^{th}$ smallest element lies within the left partition:
- Array base: a
- Subarray size: left_end
- Target rank: k
  Call: kth_smallest(a, left_end, k).

If left_end + 1 < k, the target element lies in the right partition:
- Array base: a + left_end + 1
- Subarray size: $n - (\text{left\_end} + 1) = n - \text{left\_end} - 1$
- Target rank: $k - (\text{left\_end} + 1) = k - \text{left\_end} - 1$
  Call: kth_smallest(a + left_end + 1, n - left_end - 1, k - left_end - 1).

This matches option A.

Final answer

Common trap

Passing the original array pointer a without adjusting the base pointer to the right subarray in option B.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 2
Question: 55 of 65, printed as CS Q.45
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source