Created
September 17, 2017 19:34
-
-
Save snahor/a4a765e8b2aef5b9bfd1e4216f983e67 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"sort" | |
) | |
func partition(xs []int, left, right, pivotIndex int) int { | |
pivot := xs[pivotIndex] | |
partitionIndex := left | |
xs[pivotIndex], xs[right] = xs[right], xs[pivotIndex] | |
for i := left; i < right; i++ { | |
if xs[i] < pivot { | |
xs[i], xs[partitionIndex] = xs[partitionIndex], xs[i] | |
partitionIndex++ | |
} | |
} | |
xs[right], xs[partitionIndex] = xs[partitionIndex], xs[right] | |
return partitionIndex | |
} | |
func medianOfMedians(xs []int, left, right int) int { | |
if right-left < 5 { | |
sort.Ints(xs[left : right+1]) | |
return left + (right-left)/2 | |
} | |
groupCount := 0 | |
for i := left; i < right+1; i += 5 { | |
subright := i + 4 | |
if subright > right { | |
subright = right | |
} | |
m := medianOfMedians(xs, i, subright) | |
j := left + (i-left)/5 | |
// move median to the beginning of the chunk | |
xs[m], xs[j] = xs[j], xs[m] | |
groupCount++ | |
} | |
return medianOfMedians(xs, left, left+groupCount-1) | |
} | |
func quickselect(xs []int, left, right, kth int) int { | |
if left == right { | |
return xs[left] | |
} | |
//pivotIndex := left + rand.Intn(right-left+1) | |
pivotIndex := medianOfMedians(xs, left, right) | |
pivotIndex = partition(xs, left, right, pivotIndex) | |
targetIndex := kth - 1 | |
if targetIndex == pivotIndex { | |
return xs[pivotIndex] | |
} else if targetIndex < pivotIndex { | |
return quickselect(xs, left, pivotIndex-1, kth) | |
} else { | |
return quickselect(xs, pivotIndex+1, right, kth) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment