Minimum and Maximum
Given an array \(\[1...n\]\), find the maximum and minimum number in this array.
Naive Approach
It should take \[2(n-1)\] comparison to find the maximum and minimum number in the array by iterating the array twice. It seems to exist a "smarter" way to find both min and max in one pass.
Simultaneous min and max solution
1539174266665
Selection in Expected Linear Time
Given an array \(\[1...n\]\), find the \(i^{th}\) smallest number in this array.
The solution is the same as the partition function in quick sort.
1539175417111
def Randomized_Select(A, p, r, i):
# for the initial array, p = 0, r = n - 1
# A: array
# i: ith smallest number
if p == r:
return A[p]
q = Partition(A, p, r)
k = q - p + 1
# the pivot is the value of answer
if i == k:
return A[q]
# left
elif i < k:
return Randomized_Select(A, p, q - 1, i)
# right
else:
return Randomized_Select(A, q + 1, r, i - k)Analysis
\[ T(n)\le \frac{1}{n}\cdot\sum_{k=1}^{n}T(max(k-1,n-k))+O(n) \]
We have
\[ max(k-1,n-k)=\begin{cases} k-1 & if\ k\ >\lfloor n/2\rfloor \\ n-k & if\ k\leqslant \lfloor n/2\rfloor \end{cases} \]
\[ =2k \]
Therefore,
\[ T(n)\le \frac{2c}{n}\sum_{k=n/2}^{n}k+O(n) \]
\[ =\frac{2c}{n}(\frac{n^2-n}{2}-\frac{n^2/4-3n/2+2}{2})+an \]
\[ =\frac{c}{n}(\frac{3n^2}{4}+\frac{n}{2}-2)+an \]
\[ =c(\frac{3n}{4}+\frac{1}{2}-\frac{2}{n})+an \]
\[ \le \frac{3cn}{4}+\frac{c}{2}+an \]
\[ =cn-(\frac{cn}{4}-\frac{c}{2}-an) \]
when \[n\geqslant \frac{c/2}{c/4-a} =\frac{2c}{c-4a}\], \[T(n)=O(n)\]
Selection in Worst Case
- Delete roughly 30% of element by partitioning
- At least 1/2 of 5 element median \(\le\) x
- At least $n/5/2=n/10$, median \(\le\) x
- At least \(3\cdot \lfloor n/10\rfloor\) element \(\le\) x
1539249591978
- Let C(N) = # comparison on a file of size N
1539317460536
After the calculation, the \(T(n)=O(n)\)
1539318426134
Assume \(T(n)\le20c\ N\)
\[ \begin{array}{l} T( N) =T(\lfloor N/5\rfloor ) +T( N-3\lfloor N/10\rfloor ) +O( N)\\ \ \ \ \ \ \ \ \ \leqslant 20c\ \lfloor N/5\rfloor +\ 20c\ ( N-3\lfloor N/10\rfloor ) +cN\\ \ \ \ \ \ \ \ \ =4c\ \lfloor N\rfloor \ +14c\ \lfloor N\rfloor \ +cN\\ \ \ \ \ \ \ \ \ \leqslant 20c\ \lfloor N\rfloor \end{array} \]
Reference
[1] http://www.cs.princeton.edu/~wayne/cs423/lectures/selection-4up.pdf