in Algorithms edited by
12,891 views
53 votes
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

  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)$
in Algorithms edited by
12.9k views

4 Comments

Thanks for the explanation @chauhansunil20th

0
0
edited by

Poorly framed question. "it moves the pivot so that the pivot is the last element of TO the left part" 

0
0

 pivot is the last element of the left part

why it is not counted?

1
1

7 Answers

34 votes
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.

edited by
by

4 Comments

Since a is an array so can we  do such type of operation ??   a+(a+left_end+1) 

I think we can do such increments only with pointers  not with array names.

1
1
But return value of partition is no of elements in left part which is 5
0
0

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

Someone fix this typo in the best answer, it should be      n-left_end-1

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

4 Comments

In question left part also includes pivot( mentioned in question)... We should also count pivot in total no. Of elements in left part
0
0
i think after first step of partition it would be 1 4 3 2 5 7 6 10 9 8
1
1
As it is given that the pivot is last element of the left part then the left part should contain all the elements in the left part plus pivot itself so the function should return the no of values less than or equal to pivot. But why you take that the function return no of values lesser than pivot?
1
1
8 votes
8 votes
Ans A.

4 Comments

how does the partition algorithm works when first element is pivot?how is the algorithm changed when pivot is last element?
0
0
yes,this is confusing that whether it returns number of elements on left part including pivot or not?

But if we look at code's first statement ,it means that it returns number of elements on left excluding pivot
1
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
0 votes
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.

Answer:

Related questions