better quicksort

1 files changed, 35 insertions, 8 deletions

diff --git a/sort/quick.go b/sort/quick.go
index b6dd427..f3502e5 100644
--- a/sort/quick.go
+++ b/sort/quick.go
@@ -2,10 +2,10 @@ package sort
 
 import (
 	"algorithms/ds"
+	"math/rand"
 )
 
 func Quick(a ds.ArrayList) ds.ArrayList {
-	Shuffle(a)
 	quick(a)
 	return a
 }
@@ -22,15 +22,13 @@ func quick(a ds.ArrayList) {
 }
 
 func quickPartition(a ds.ArrayList) int {
-	i := 0      // Left scan index
-	j := len(a) // Right scan index
+	l := len(a)
+	i := 0 // Left scan index
+	j := l // Right scan index
 	hi := j - 1
 
-	// Median of first 3 elems is partitioning item
-	// This works because we randomly shuffled a in the beginning
-	Insertion(a[0:3])
-	a.Swap(0, 1)
-	v := a[0] // Partitioning item
+	a.Swap(0, median(a, l))
+	v := a[0]
 
 	for {
 		for i++; a[i] < v && i < hi; i++ {
@@ -53,3 +51,32 @@ func quickPartition(a ds.ArrayList) int {
 	// whith a[lo..j-1 <= a[j] <= a[j+1..hi]
 	return j
 }
+
+func median(a ds.ArrayList, l int) int {
+	u := rand.Intn(l)
+	v := rand.Intn(l)
+	w := rand.Intn(l)
+
+	x := a[u]
+	y := a[v]
+	z := a[w]
+
+	if x < y {
+		switch {
+		case y < z:
+			return v
+		case x < z:
+			return w
+		default:
+			return u
+		}
+	}
+	switch {
+	case x < z:
+		return u
+	case y < z:
+		return w
+	default:
+		return v
+	}
+}