add parallelquick and so on

1 files changed, 82 insertions, 40 deletions

diff --git a/sort/sort_test.go b/sort/sort_test.go
index 3a44827..899669b 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -10,61 +10,68 @@ import (
 var benchResult ds.ArrayList
 var benchResultInt []int
 
+const minLength int = 100
 const maxLength int = 10000
 
+var arrayListCache map[string]ds.ArrayList
+
 type sortAlgorithm func(ds.ArrayList) ds.ArrayList
 type sortAlgorithmInt func([]int) []int
 
 func TestSelectionSort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		test(Selection, i, t)
 	}
 }
 
 func TestInsertionSort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		test(Insertion, i, t)
 	}
 }
 
 func TestShellSort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		test(Shell, i, t)
 	}
 }
 
 func TestMergeSort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		test(Merge, i, t)
 	}
-	test(Merge, maxLength*2, t)
 }
 
-func TestMerge2Sort(t *testing.T) {
+func TestBottomUpMergeSort(t *testing.T) {
 	t.Log("Parallel merge sort")
-	for i := 1; i <= maxLength; i *= 10 {
-		test(Merge2, i, t)
+	for i := minLength; i <= maxLength; i *= 10 {
+		test(BottomUpMerge, i, t)
 	}
-	test(Merge2, maxLength*2, t)
+	test(BottomUpMerge, maxLength*2, t)
 }
 
-func TestMerge3Sort(t *testing.T) {
+func TestParallelMergeSort(t *testing.T) {
 	t.Log("Bottom-up merge sort")
-	for i := 1; i <= maxLength; i *= 10 {
-		test(Merge3, i, t)
+	for i := minLength; i <= maxLength; i *= 10 {
+		test(ParallelMerge, i, t)
 	}
-	test(Merge3, maxLength*2, t)
 }
 
 func TestQuickSort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		test(Quick, i, t)
 	}
 }
 
-func TestQuick2Sort(t *testing.T) {
-	for i := 1; i <= maxLength; i *= 10 {
-		test(Quick2, i, t)
+func TestParallelQuickSort(t *testing.T) {
+	for i := minLength; i <= maxLength; i *= 10 {
+		test(ParallelQuick, i, t)
+	}
+}
+
+func TestQuick3WaySort(t *testing.T) {
+	for i := minLength; i <= maxLength; i *= 10 {
+		test(Quick3Way, i, t)
 	}
 }
 
@@ -75,63 +82,71 @@ func TestShuffleSort(t *testing.T) {
 }
 
 func BenchmarkInsertionSort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		benchmark(Insertion, i, b)
 	}
 }
 
 func BenchmarkSelectionSort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		benchmark(Selection, i, b)
 	}
 }
 
 func BenchmarkShellSort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		benchmark(Shell, i, b)
 	}
 }
 
 func BenchmarkMergeSort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		benchmark(Merge, i, b)
 	}
 }
 
-func BenchmarkMerge2Sort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
-		benchmark(Merge2, i, b)
+func BenchmarkBottomUpMergeSort(b *testing.B) {
+	for i := minLength; i <= maxLength; i *= 10 {
+		benchmark(BottomUpMerge, i, b)
 	}
 }
 
-func BenchmarkMerge3Sort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
-		benchmark(Merge3, i, b)
+func BenchmarkParallelMergeSort(b *testing.B) {
+	for i := minLength; i <= maxLength; i *= 10 {
+		benchmark(ParallelMerge, i, b)
 	}
 }
 
 func BenchmarkQuickSort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		benchmark(Quick, i, b)
 	}
 }
 
-func BenchmarkQuick2Sort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
-		benchmark(Quick2, i, b)
+func BenchmarkParallelQuickSort(b *testing.B) {
+	for i := minLength; i <= maxLength; i *= 10 {
+		benchmark(ParallelQuick, i, b)
 	}
 }
 
+func BenchmarkQuick3WaySort(b *testing.B) {
+	for i := minLength; i <= maxLength; i *= 10 {
+		benchmark(Quick3Way, i, b)
+	}
+}
+
+/*
 func BenchmarkShuffleSort(b *testing.B) {
-	for i := 1; i <= maxLength; i *= 10 {
+	for i := minLength; i <= maxLength; i *= 10 {
 		benchmark(Shuffle, i, b)
 	}
 }
+*/
 
 func test(sort sortAlgorithm, length int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
-		a := makeIntegers(length, length)
+		a := makeRandomIntegers(length, -1)
 		a = sort(a)
 		if !a.Sorted() {
 			t.Errorf("Array not sorted: %v", a)
@@ -143,7 +158,7 @@ func test(sort sortAlgorithm, length int, t *testing.T) {
 func testShuffle(sort sortAlgorithm, length int, t *testing.T) {
 	cb := func(t *testing.T) {
 		t.Parallel()
-		a := sort(ds.SortedIntegers(length))
+		a := sort(ds.AscendingIntegers(length))
 		if a.Sorted() {
 			t.Errorf("Array sorted: %v", a.FirstN(10))
 		}
@@ -152,16 +167,43 @@ func testShuffle(sort sortAlgorithm, length int, t *testing.T) {
 }
 
 func benchmark(sort sortAlgorithm, length int, b *testing.B) {
-	cb := func(b *testing.B) {
-		a := makeIntegers(length, length)
+	a := makeRandomIntegers(length, -1)
+	b.Run(fmt.Sprintf("random(%d)", length), func(b *testing.B) {
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			benchResult = sort(a)
 		}
-	}
-	b.Run(fmt.Sprintf("%d", length), cb)
+	})
+
+	a = ds.AscendingIntegers(length)
+	b.Run(fmt.Sprintf("ascending(%d)", length), func(b *testing.B) {
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			benchResult = sort(a)
+		}
+	})
+
+	a = ds.DescendingIntegers(length)
+	b.Run(fmt.Sprintf("descending(%d)", length), func(b *testing.B) {
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			benchResult = sort(a)
+		}
+	})
 }
 
-func makeIntegers(length, max int) ds.ArrayList {
-	return ds.RandomIntegers(length, max)
+func makeRandomIntegers(length, 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)", length, max)
+	if a, ok := arrayListCache[key]; ok {
+		return a
+	}
+	a := ds.RandomIntegers(length, max)
+	arrayListCache[key] = a
+	return a
 }