Added Quickselect in Go

phoebeclarke · phoebeclarke · commit 8738fe1b19b7 · 2017-10-15T12:09:34.000+01:00
diff --git a/QuickSelect/Go/QuickSelect.go b/QuickSelect/Go/QuickSelect.go
@@ -0,0 +1,50 @@
+package main
+
+import (
+	"math/rand"
+)
+
+func quickselect(list []int, item_index int) int {
+	return selec(list,0, len(list) - 1, item_index)
+}
+
+func partition(list []int, left int, right int, pivotIndex int) int {
+	pivotValue := list[pivotIndex]
+
+	// move pivot to end
+	list[pivotIndex], list[right] = list[right], list[pivotIndex]
+
+	storeIndex := left
+
+	for i := left; i < right; i++ {
+		if list[i] < pivotValue {
+			// move pivot to its final place
+			list[storeIndex], list[i] = list[i], list[storeIndex]
+			storeIndex += 1
+		}
+	}
+	list[right], list[storeIndex] = list[storeIndex], list[right]
+
+	return storeIndex
+}
+
+func selec(list []int, left int, right int, k int) int {
+
+	if left == right {
+		return list[left]
+	}
+
+	pivotIndex := rand.Intn(right)
+	// the pivot in its final sorted position
+	pivotIndex = partition(list, left, right, pivotIndex)
+
+	if k == pivotIndex {
+		return list[k]
+	} else if k < pivotIndex {
+		return selec (list, left, pivotIndex - 1, k)
+	} else {
+		return selec(list, pivotIndex + 1, right, k)
+	}
+}
+
+func main() {}
diff --git a/README.md b/README.md
@@ -39,6 +39,7 @@ MiniMaxWithABPruning | :+1: |  |  |  |  |  |  |  |
 Modified_Binary_Search |  |  |  | :+1: |  |  |  |  |
 Postman Sort |  |  |  | :+1: |  |  |  |  |
 Quick Sort | :+1: | :+1: |  |  |  | :+1: | :+1: | :+1: |  :+1:
+Quick Select | | | | | :+1: | | |
 Uniform-cost search | :+1: |  |  |  |  | :+1: | :+1: |  |
 RadixSort | :+1: | :+1: |  |  | :+1: |  |  |  |
 RobinCarp | :+1: |  |  |  |  |  |  |  |
