1. Sort and find: O(nlogn)
2. Quick Select: O(n)
Quick Select: It is similar to Quick Sort about partitioning, but it does not need to sort all elements in an array. The most important thing is the location of pivot. If k, an index of the array, is less than an index of pivot, we need to care about only left part of k. We do not need to worry about a right side of pivot.
Ideal case: n + n/2 + n/4 + .... = n(1 + 1/2 + 1/4 + ....) = n ( 1 / (1 - 1/2) ) = 2n = O(n)
* Sn = a + ar + ar^2 + ar^3 + ... + ar^(n-2) + ar^(n-1) = a / (1 - r)
QuickSelect.groovy
def swap(list, a, b) {
def temp = list[a]
list[a] = list[b]
list[b] = temp
}
def partition(list, pivot, left, right) {
def storeIdx = left
swap(list, pivot, right)
for(int i = left; i < right; ++i) {
if(list[i] < list[right]) {
swap(list, i, storeIdx)
storeIdx++
}
}
swap(list, storeIdx, right)
return storeIdx
}
def select(list, k, left, right) {
while(true) {
def pivot = new Random().nextInt(right - left +1) + left
println "pivot = " + pivot
def newPivot = partition(list, pivot, left, right)
println list
if(k == newPivot) {
return list[k]
} else if (newPivot < k) {
left = newPivot + 1
} else {
right = newPivot - 1
}
}
}
def list = [9,8,7,4,5,0,2,1,6,3]
def left = 0
def right = list.size() - 1
def k = new Random().nextInt(right - left + 1 ) + left
println "k = " + k
println list
def answer = select(list, k, left, right)
println "[ANSWER] " + answer
'Computer Science > Algorithm' 카테고리의 다른 글
| quick sort - Java (0) | 2011.05.30 |
|---|---|
| quick sort - c (0) | 2011.05.30 |
| insertion sort - c (0) | 2011.05.28 |
| insertion sort - Java (0) | 2011.05.26 |
| binary search - Java (0) | 2011.05.17 |
