9.2 Selection in expected linear time
9.2-1
If an array has 0 length, we have q - p = 0
or r - q = 0
. If q - p = 0
, we have k = 1
and line 8 will be executed, but we have i < k
, so i < 1
, which is not possible. If r - q = 0
, we have i > k
, but k = q - p + 1 = r - p + 1
, so k
is the length of array, thus i
could not be larger than k
.
So the algorithm never makes a recursive call to a 0-length array.
9.2-2
The value of $X_k$ doesn't affect the subproblem T(max(k - 1, n - k)). So they are independent.
9.2-3
RANDOMIZED-SELECT(A, p, r, i)
while p <= r
if p == r
return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1
if i = k
return A[q]
elseif i < k
r = q - 1
else
p = q + 1
i = i - k
9.2-4
The worst-case happens when the partition procedure always select the largest element as pivot.
pivot = 9, subarray = { 3, 2, 1, 0, 7, 5, 4, 8, 6}
pivot = 8, subarray = { 3, 2, 1, 0, 7, 5, 4, 6 }
pivot = 7, subarray = { 3, 2, 1, 0, 6, 5, 4 }
pivot = 6, subarray = { 3, 2, 1, 0, 4, 5 }
pivot = 5, subarray = { 3, 2, 1, 0, 4}
pivot = 4, subarray = { 3, 2, 1, 0 }
pivot = 3, subarray = { 0, 2, 1 }
pivot = 2, subarray = { 0, 1 }
pivot = 1, subarray = { 0 }
minimum = 0