Minimum, Maximum, Order Statistics
Notes
- Given an unorderd array, what is the expected time for finding the minimum or maximum value?
-
MINIMUM(A) A: An unordered array
- min ← A[0]
- for i ← 1 to A.size-1 do
- if min > A[i]
- min = A[i]
- return min
- This clearly works
- And reversing the comparison would work for max
- CLRS argues that
This could be considered a tournment among the values And each value but the min must lose once So we need n-1 comparisons to determine the min/max in the worst case So this is the best we can do.
-
- The Selection Problem: given an array A with n elements, find the element that would be in position i, 0 ≤ i < n
- An obvious solution is
-
SELECT(A,i) A: an unordered array i: an integer 0 ≤ i < A.size
- B = sort(A)
- return B[i]
- This is clearly O(n log2 n)
-
- We could use quicksort's pivot function
- Pivot the array, if the pivot position is i, return, otherwise pivot the sub array i would be in.
PARTITION-SELECT(A, i, low, high) A: an unordered array i: an integer 0 ≤ i < A.size low and high, valid positions in the array such that low ≤ i ≤ high- if low = high
- return A[low]
- part ← Partition(A, low, high)
- if i == part
- return A[part]
- if i < part
- return PARTITION_SELECT(A, i, low, part-1)
- else
- return PARTITION_SELECT(A, i, part+1, high)
- This is O(n2) in the worst case.
- But it does either take extra space or it scrambles the array.
- Complex to compute, but average time will be O(n)
- Pivot the array, if the pivot position is i, return, otherwise pivot the sub array i would be in.