GATE CS 2015 Set 2 — Question 49
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67MediumSelection (Order Statistics)SearchingAlgorithmsFunctions & RecursionC ProgrammingProgramming & Data StructuresArrays & Strings in C
Algorithms → C Programming → Arrays & Strings in C
Last updated
Question
Suppose you are provided with the following function declaration in the C programming language.The function treats the first element of The missing argument lists are respectively
int partition(int a[], int n);
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 smallest element in an array a[] of size n using the partition function. We assume .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( ___________ );
}
}
Correct answer
(A) (a, left end, k) and (a+left end+1, n-left end-1, k-left end-1)
Solution
The function
partition returns left_end, which is the number of elements in the left part (including the pivot). The pivot is placed at a[left_end]. Wait, the problem states the pivot is the last element of the left part. If the return value is the number of elements in the left part, say , then the left part occupies indices to , and the pivot is at .However, the code checks if ( left_end+1 == k ). This implies that left_end is treated as the index of the pivot in a 0-indexed array (where the pivot is the -th element). If left_end is the index, then the number of elements in the left subarray (excluding pivot) is left_end (indices to ).Let's assume standard QuickSelect logic where partition returns the index of the pivot.- If , the pivot is the -th element.
- If , the -th element is in the left subarray . The recursive call should be on the same array pointer
a, sizep(which isleft_end), and samek. Argument:(a, left_end, k). - If , the -th element is in the right subarray . The recursive call should be on
a + p + 1, sizen - (p + 1), and we need the -th element of this new subarray. Argument:(a + left_end + 1, n - left_end - 1, k - left_end - 1).
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on C Programming
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 2 Q24Consider the following functions, where is a positive integer.…