Thanks for the explanation @chauhansunil20th

Dark Mode

12,891 views

53 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

34 votes

Best answer

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.

1

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**).

0

1

8 votes

0

1

in first go I'm also include the pivot element in left part, it's very ambiguous that we have to include the pivot or not. But if we think deeply they mentioned

"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."

this mean they said we have to include it that's why we got infinite recursion for some sequence.

0

0 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.