You know two strategies for selecting k top-rank achievers (by GPA) in an unorde
ID: 3831168 • Letter: Y
Question
You know two strategies for selecting k top-rank achievers (by GPA) in an unordered list of GPA records for n university students: (a) Run k times quickselect with linear processing time, T_qselect (n) = cn, in order to sequentially fetch the students of the rank n, n - 1, and so on up to n - k + 1, or (b) Run once quicksort with linearithmic processing time, T_qsort (w) = enlog_2 n, to sort the entire list in ascending GPA order and fetch the k top-rank students. Let both the algorithms have the same factor c and let data fetching take negligibly small time, comparing to sorting. Find out, in terms of k and n, when Option 6a is faster than Option 6b, and determine the fastest option for k = 10 and n = 32, 768 = 2^15.Explanation / Answer
QuickSelect(S, k)
let r be chosen uniformly at random in the range 1 to length(S)
let pivot = S[r]
let S1, S2 be new arrays
# split into a pile S1 of small elements and S2 of big elements
for i = 1 to n
if S[i] < pivot then
append S[i] to S1
else if S[i] > pivot then
append S[i] to S2
else
# do nothing
end for
if k >= length(S1):
# it's in the pile of small elements
return QuickSelect(S1, k)
else if k < length(S) - length(S2)
# it's in the pile of big elements
return QuickSelect(S2, k - (length(S) - length(S2))
else
# it's equal to the pivot
return pivot
algorithm quick sort(S, lo, hi) is
if lo < hi then
p := partition(S, lo, hi)
quicksort(S, lo, p)
quicksort(S, p + 1, hi)
algorithm partition(S, lo, hi) is
pivot := S[lo]
i := lo – 1
j := hi + 1
loop forever
do
i := i + 1
while S[i] < pivot
do
j := j – 1
while S[j] > pivot
if i >= j then
return j
swap S[i] with S[j]
T(n) = O(n) + 2T(n/2)
from master theorem u get T(n)=O(nlogn).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.