fix test

2 files changed, 14 insertions, 30 deletions

diff --git a/sort/quick.go b/sort/quick.go
index 7222515..b6dd427 100644
--- a/sort/quick.go
+++ b/sort/quick.go
@@ -26,21 +26,17 @@ func quickPartition(a ds.ArrayList) int {
 	j := len(a) // 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
 
 	for {
-		for i++; a[i] < v; i++ {
-			if i == hi {
-				break
-			}
+		for i++; a[i] < v && i < hi; i++ {
 		}
 
-		for j--; v < a[j]; j-- {
-			if j == 0 {
-				break
-			}
+		for j--; v < a[j] && j > 0; j-- {
 		}
 
 		// Check scan complete
diff --git a/sort/sort_test.go b/sort/sort_test.go
index 475c179..07ac2bf 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -8,7 +8,6 @@ import (
 
 // Store results here to avoid compiler optimizations
 var benchResult ds.ArrayList
-var benchResultInt []int
 
 const minLength int = 1
 const maxLength int = 10000
@@ -147,7 +146,7 @@ func BenchmarkShuffleSort(b *testing.B) {
 func test(sort sortAlgorithm, l int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
-		a := makeRandomIntegers(l, -1)
+		a := ds.NewRandomArrayList(l, -1)
 		a = sort(a)
 		if !a.Sorted() {
 			t.Errorf("Array not sorted: %v", a)
@@ -168,11 +167,14 @@ func testShuffle(sort sortAlgorithm, l int, t *testing.T) {
 }
 
 func benchmark(sort sortAlgorithm, l int, b *testing.B) {
-	a := makeRandomIntegers(l, -1)
+	a := ds.NewRandomArrayList(l, -1)
+	aux := ds.NewArrayList(l)
+
 	b.Run(fmt.Sprintf("random(%d)", l), func(b *testing.B) {
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
-			benchResult = sort(a)
+			copy(aux, a)
+			benchResult = sort(aux)
 		}
 	})
 
@@ -180,7 +182,8 @@ func benchmark(sort sortAlgorithm, l int, b *testing.B) {
 	b.Run(fmt.Sprintf("ascending(%d)", l), func(b *testing.B) {
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
-			benchResult = sort(a)
+			copy(aux, a)
+			benchResult = sort(aux)
 		}
 	})
 
@@ -188,23 +191,8 @@ func benchmark(sort sortAlgorithm, l int, b *testing.B) {
 	b.Run(fmt.Sprintf("descending(%d)", l), func(b *testing.B) {
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
-			benchResult = sort(a)
+			copy(aux, a)
+			benchResult = sort(aux)
 		}
 	})
 }
-
-func makeRandomIntegers(l, max int) ds.ArrayList {
-	// Use a cache to make sure that all all sorting algos use the same
-	// random sequences.
-	if arrayListCache == nil {
-		arrayListCache = make(map[string]ds.ArrayList)
-	}
-
-	key := fmt.Sprintf("random(%d, %d)", l, max)
-	if a, ok := arrayListCache[key]; ok {
-		return a
-	}
-	a := ds.NewRandomArrayList(l, max)
-	arrayListCache[key] = a
-	return a
-}