Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
0 votes
367 views
in Information Technology by (115k points)
closed by

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 ktℎ smallest element in an array a[ ] of size n using the partition function. We assume 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( _____________________ );

      } else {

                return kth_smallest( _____________________ );

      }

}

The missing argument 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)

1 Answer

0 votes
by (152k points)
selected by
 
Best answer
Correct Answer - Option 1 : (a, left_end, k) and (a + left_end + 1, n - left_end - 1, k - left_end - 1)

We have to find the kth smallest element.

Condition is : if (left_end + 1 > k)

If this condition is true it means kth smallest element is present of left side. So a recursive call is done to kth_smallest(a, left_end,k);

If condition becomes false and left_end+ 1 is not equal to k, then kth smallest element will be present of right side of array. So, a recrusive call will be done as :

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

Example:

Consider an array of 10 numbers i.e. N= 10, k= 7

a= {5,4,3,2,1,7,6,10,9,8}

pivot = 5

Step 1: after partition array will be = {4,3,2,1,5,7,6,10,9,8}

Here, left_end = 4

if(left_end < k)                         //else condition is satisifed

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

it will become (a+5, 5, 3)

array a = {7, 6, 10, 9, 8}

pivot = 7

STEP 2: After partition ()

Array = {6,7,10, 9, 8}

Left_end = 1

if(Left_end + 1 < k)               // else condition is satisfied

so, (a+2, 3, 1)

array a = {10, 9, 8}

pivot = 10

STEP 3: After partition ()

Array a = {9, 8, 10}

Left_end = 2

Again left_end + 1 > k           // if condition satisified

So, (a, 2, 1)

Array a = {9, 8}

Pivot = 9

STEP 4:

Array = {8,9}

Left _ end = 1

Left_end +1 > k                  // if condition satisifed

So, (a,1,1)

Array = {8}

Pivot = 8

STEP 8: here, left_end = 0,

Left_end + 1 ==k , a[left_end ]= 8

At the end, it returns the left_end value.

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...