Skip to content

Instantly share code, notes, and snippets.

@snahor
Created September 17, 2017 19:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save snahor/a4a765e8b2aef5b9bfd1e4216f983e67 to your computer and use it in GitHub Desktop.
Save snahor/a4a765e8b2aef5b9bfd1e4216f983e67 to your computer and use it in GitHub Desktop.
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