The GATE Grind

GATE 2015 CS (CS2) – Question 49

Algorithms · Divide-and-Conquer · 2 marks · Multiple choice

partition(a,n) uses a[0] as pivot, moves values ≤pivot left and greater values right, and places the pivot last in the left part. Complete the recursive argument lists for kth_smallest, with 1≤k≤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(/* first */);
  else return kth_smallest(/* second */);
}
  1. (a,left_end,k); (a+left_end+1,n−left_end−1,k−left_end−1)
  2. (a,left_end,k); (a,n−left_end−1,k−left_end−1)
  3. (a+left_end+1,n−left_end−1,k−left_end−1); (a,left_end,k)
  4. (a,n−left_end−1,k−left_end−1); (a,left_end,k)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) (a,left_end,k); (a+left_end+1,n−left_end−1,k−left_end−1)

Explanation

The pivot rank is left_end+1 in this function’s zero-based index convention. A smaller rank recurses on the left_end preceding elements with k unchanged. A greater rank skips those elements plus the pivot, reducing both length and rank by left_end+1 and advancing the pointer. This is A. The source prose’s count wording is interpreted through its explicit code convention.

More Divide-and-Conquer questions

All Divide-and-Conquer questions →