Suppose you are provided with the following function declaration in the C…
2015
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)
Attempted by 104 students.
Show answer & explanation
Correct answer: A
Key insight: partition(a,n) returns the pivot's final index (call it left_end). The left side contains left_end+1 elements including the pivot, and the pivot is at a[left_end].
If left_end+1 == k: the pivot is the k-th smallest, so return a[left_end].
If left_end+1 > k: the k-th smallest lies in the left subarray a[0..left_end-1], which has length left_end. Recurse with kth_smallest(a, left_end, k).
If left_end+1 < k: the k-th smallest lies in the right subarray starting at a+left_end+1 with length n-left_end-1. Its rank inside that subarray is k-(left_end+1), so recurse with kth_smallest(a+left_end+1, n-left_end-1, k-left_end-1).
Therefore the two missing argument lists are: (a, left_end, k) for the left recursion and (a+left_end+1, n-left_end-1, k-left_end-1) for the right recursion.