quickselect.go

package quickselect

func Quickselect(data []int, k, left, right int) {
	var t, i, j int
	for right > left {
		t = data[k]
		i = left
		j = right

		swap(data, left, k)
		if compare(data[right], t) > 0 {
			swap(data, left, right)
		}

		for i < j {
			swap(data, i, j)
			i++
			j--
			for compare(data[i], t) < 0 {
				i++
			}
			for compare(data[j], t) > 0 {
				j--
			}
		}

		if compare(data[left], t) == 0 {
			swap(data, left, j)
		} else {
			j++
			swap(data, j, right)
		}

		if j <= k {
			left = j + 1
		}
		if k <= j {
			right = j - 1
		}
	}
}

func swap(data []int, i, j int) {
	data[i], data[j] = data[j], data[i]
}

func compare(a, b int) int {
	if a < b {
		return -1
	}
	if b < a {
		return 1
	}
	return 0
}

Would be nice to accept sort.Interface rather than a concrete type. Hard because the starting value at position k for each loop gets swapped before later comparisons that need it.