GATE CSE 2015 | Set 2 | Question: 45

Question

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

• A. $(a,$ left_end$, k) $ and $ (a+$left_end$+1, n-$left_end$-1, k-$left_end$-1)$
• B. $(a,$ left_end$, k) $ and $ (a, n-$left_end$-1, k-$left_end$-1)$
• C. $(a+$ left_end$+1, n-$left_end$-1, k-$left_end$-1) $ and $(a, $ left_end$, k)$
• D. $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$

Comments

@Shaik Masthan sir in this question i was putting options and trace it so luckily in this question 1st option itself is true. But if 4th option is true then it will take lot of time according to my approach. Can you suggest any other way(for exam)?

Thanks

---

I think eliminating option by taking an example ( like u did) will be best approach in exam.

---

pivot must not be added to left part, if so, code wiil not work properly. function partition must return size of array without pivot

Answer 1

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.

Comments

@sanjaysharmarose

since array name is nothing but base address of array, hence we can do such types of operations.

---

Here I think there is a problem in the question itself. Suppose we need to find third smallest element (k=3). They are saying left_end has number of elements in the left subarray but the logic is written as if left_end is the index of the pivot. Suppose the index of pivot is 2 then the number of elements in the left_subarray are 3 (0,1,2). So how come 3+ 1 == 3. The correct statement should be that left_end is the last index in the left_subarray.

---

The Question states that the partition function always takes the first element of the array as pivot and the parameters for it are (a[], n) where n is size of array so if element is in right portion of array how will we ever get it via partition if it never takes an input for starting index of array?

Answer 2

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

Comments

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?

---

Question is not framed properly. The partition should return the index of the pivot and not the number of elements in the left_array.

---

it does return that, that's why +1 is added to left_end so that it can represent the no. of elements in the left part

Answer 3

Ans A.

Comments

how does the partition algorithm works when first element is pivot?how is the algorithm changed when pivot is last element?

---

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

---

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.

Answer 4

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 5

QuickSort is used as a sorting algorithm.In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot.

Answer 6

Consider an array A:

n=5

3

6

2

1

4

We apply partition function as partition(A, 5).​​​​​​

'3' is the pivot element.

So after partition function, we have:

2

1

3

6

4

So, Left_End=2 i.e. number of element on the left side of '3'. Exclude 3 from the count.

Now suppose k=2

Left_End+1=3 ( !=2)

Now, k<Left_End+1

Now, 2nd smallest element should be the the 2nd element of the left subarray of 3 if it was sorted.

So 'k' remains 2, size of the subarray=2 and array starts from A.

So first statement will be:

(A,2,2): (a, Left_End, k)

Now, if k=4

Left_End+=3 (!=4)

Now, k>Left_End+1

So, 4th smallest element would be the first element of right subarray if it was sorted.

So 'k' becomes 1, size of the array=2 and we start from index=3 ( a+3 )

So second statement will be

(A+3, 2, 1): ( a+left_end+1, n-(left_end+1), k-(left_end+1))

Hence, option A would be thr right answer.

​​​