Write down the pseudocode for Partition procedure in O(n) time. Input: array a[1..n], integer i Output:...

Transcribed Image Text:

Write down the pseudocode for Partition procedure in O(n) time. Input: array a[1..n], integer i Output: the ith largest element in a 1: If n 60, then find the ith largest element by sorting. 2: Divide the n elements in [n/5] groups of 5 elements. At most 4 elements remain. 3: Find the median of each of the [n/5] groups by sorting. 4: Recursively call Select to find the median m of the [n/5] medians. (Once we found m, we forget about the groups.) 5: Use the procedure Partition on a with m as the pivot element. 6: Let q be the position of m in the array. 7: If qi, then return m. 8: If i < q, then call Select(a[1..q-1], i). Else call Select (alg +1..n], i-q). 1 r = [n/5] ^ и и ✓ . a Write down the pseudocode for Partition procedure in O(n) time. Input: array a[1..n], integer i Output: the ith largest element in a 1: If n 60, then find the ith largest element by sorting. 2: Divide the n elements in [n/5] groups of 5 elements. At most 4 elements remain. 3: Find the median of each of the [n/5] groups by sorting. 4: Recursively call Select to find the median m of the [n/5] medians. (Once we found m, we forget about the groups.) 5: Use the procedure Partition on a with m as the pivot element. 6: Let q be the position of m in the array. 7: If qi, then return m. 8: If i < q, then call Select(a[1..q-1], i). Else call Select (alg +1..n], i-q). 1 r = [n/5] ^ и и ✓ . a

Answer rating: 100% (QA)

Here is a detailed explanation The technique just sorts the array and returns the ith member if the ... View the full answer