edited by
16,413 views
55 votes
55 votes

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

  1. $(a,$ left_end$, k) $ and $ (a+$left_end$+1, n-$left_end$-1, k-$left_end$-1)$
  2. $(a,$ left_end$, k) $ and $ (a, n-$left_end$-1, k-$left_end$-1)$
  3. $(a+$ left_end$+1, n-$left_end$-1, k-$left_end$-1) $ and $(a, $ left_end$, k)$
  4. $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$
edited by

7 Answers

Best answer
38 votes
38 votes

We have to find the $k^{th}$ smallest element.

if (left_end+1 > k) 

If the above condition is true, it means we have $k^{th}$ smallest element on the left array, whose size is left_end instead of $n$ for the original array. (The "+1" is used because array index in C language starts from 0). So, we can do a recursive call as 

  • kth_smallest( a, left_end, k); 

If the above condition is false, and left_end $+1\neq k,$ it means $k^{th}$ smallest element is on the right part of the array and it will be $(k - \text{left_end}-1)^{th}$ element there as left_end+1 elements are gone in the left part. So, the recursive call will be 

  • kth_smallest( a + left_end + 1, n - left_end – 1, k - left_end - 1); 

Correct Option: A.

edited by
52 votes
52 votes

First of all, here the return value is the number of elements less than the pivot

Pivot is just to minimize searching

So, now we are assuming our array has $10$ elements, $N=10 , k=8$

STEP 1:          After Partition()

  • left_end = 4
  • left_end+1 < k
  • so, (a+left_end+1, n-left_end-1, k-left_end-1)
  • (a+5, 5, 3)

STEP 2: After  Partition()

  • left_end= 1
  • left_end+1 < k
  • so, (a+2, 3, 1)

STEP 3: After Partition()

  • left_end = 2
  • left_end +1 > k
  • so, (a, 2, 1)

STEP 4: After Partition()

  • left_end = 1
  • left_end +1 > k
  • so, (a,1,1)

STEP 5:

  • left_end = 0
  • left_end+1 = =k
  • a[left_end] = 8

So, in STEP 1 and STEP 2 'else' condition is satisfied, and STEP 3 and STEP 4 'if ' condition is satisfied.

Here, partition is called and it returns the left_end value

Answer will be (A).

edited by
8 votes
8 votes
Ans A.
1 votes
1 votes

Dry run it.

If the "if" condition is true, required element is in the left part of the array. So, we need to pass just the left part of the array, as the whole array.

If the "else" condition is true, required element is in the right part of the array. So, we need to pass just the right part of the array, as the whole array.

So, option A

 

Also, adding from Manu Thakur's comment — in the else part, we need to recursively call just the right part of the array as the complete array. It obviously won't always start with the base address (a), hence Options B, C and D are directly eliminated.

Answer:

Related questions

62 votes
62 votes
12 answers
1
go_editor asked Feb 12, 2015
20,904 views
Consider the following C function.int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (n-k); return x; }The return value of $fun(5)$...
25 votes
25 votes
3 answers
2
go_editor asked Feb 12, 2015
6,928 views
Given below are some algorithms, and some algorithm design paradigms.$$\begin{array}{ll|ll}\hline \text{1.} & \text{Dijkstra's Shortest Path} & \text{i.} & \text{Divide a...
61 votes
61 votes
6 answers
3
go_editor asked Feb 12, 2015
17,403 views
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$\Theta(n \log n)$$\Thet...
88 votes
88 votes
5 answers
4