add parallelquick and so on

9 files changed, 225 insertions, 146 deletions

diff --git a/sort/merge3.go b/sort/bottomupmerge.go
index fbc1650..e7788bb 100644
--- a/sort/merge3.go
+++ b/sort/bottomupmerge.go
@@ -4,8 +4,7 @@ import (
 	"algorithms/ds"
 )
 
-// Merge3 is the bottom up version of merge sort.
-func Merge3(a ds.ArrayList) ds.ArrayList {
+func BottomUpMerge(a ds.ArrayList) ds.ArrayList {
 	length := len(a)
 	aux := make(ds.ArrayList, length)
 
diff --git a/sort/insertion.go b/sort/insertion.go
index 3e271b0..983edf2 100644
--- a/sort/insertion.go
+++ b/sort/insertion.go
@@ -5,9 +5,12 @@ import (
 )
 
 func Insertion(a ds.ArrayList) ds.ArrayList {
-	length := len(a)
+	insertion(a, 0, len(a)-1)
+	return a
+}
 
-	for i := 0; i < length; i++ {
+func insertion(a ds.ArrayList, lo, hi int) {
+	for i := lo; i <= hi; i++ {
 		for j := i; j > 0; j-- {
 			if a[j].Higher(a[j-1]) {
 				break
@@ -15,6 +18,4 @@ func Insertion(a ds.ArrayList) ds.ArrayList {
 			a.Swap(j, j-1)
 		}
 	}
-
-	return a
 }
diff --git a/sort/merge2.go b/sort/parallelmerge.go
index 774c3c5..b6cf721 100644
--- a/sort/merge2.go
+++ b/sort/parallelmerge.go
@@ -5,15 +5,14 @@ import (
 	"sync"
 )
 
-// Merge2 is a parallelized version of Merge
-func Merge2(a ds.ArrayList) ds.ArrayList {
+func ParallelMerge(a ds.ArrayList) ds.ArrayList {
 	aux := make(ds.ArrayList, len(a))
-	mergeSort2(a, aux, 0, len(a)-1)
+	parallelMerge(a, aux, 0, len(a)-1)
 
 	return a
 }
 
-func mergeSort2(a, aux ds.ArrayList, lo, hi int) {
+func parallelMerge(a, aux ds.ArrayList, lo, hi int) {
 	mid := lo + (hi-lo)/2
 	defer merge(a, aux, lo, mid, hi)
 
@@ -26,11 +25,11 @@ func mergeSort2(a, aux ds.ArrayList, lo, hi int) {
 	var wg sync.WaitGroup
 	wg.Add(2)
 	go func() {
-		mergeSort2(a, aux, lo, mid)
+		parallelMerge(a, aux, lo, mid)
 		wg.Done()
 	}()
 	go func() {
-		mergeSort2(a, aux, mid+1, hi)
+		parallelMerge(a, aux, mid+1, hi)
 		wg.Done()
 	}()
 	wg.Wait()
diff --git a/sort/parallelquick.go b/sort/parallelquick.go
new file mode 100644
index 0000000..f68135f
--- /dev/null
+++ b/sort/parallelquick.go
@@ -0,0 +1,40 @@
+package sort
+
+import (
+	"algorithms/ds"
+	"sync"
+)
+
+func ParallelQuick(a ds.ArrayList) ds.ArrayList {
+	Shuffle(a)
+	parallelQuick(a, 0, len(a)-1)
+	return a
+}
+
+func parallelQuick(a ds.ArrayList, lo, hi int) {
+	if hi <= lo+10 {
+		insertion(a, lo, hi)
+		return
+	}
+
+	j := quickPartition(a, lo, hi)
+
+	if hi <= lo+1000 {
+		var wg sync.WaitGroup
+		wg.Add(2)
+		defer wg.Wait()
+
+		go func() {
+			parallelQuick(a, lo, j-1)
+			wg.Done()
+		}()
+		go func() {
+			parallelQuick(a, j+1, hi)
+			wg.Done()
+		}()
+		return
+	}
+
+	parallelQuick(a, lo, j-1)
+	parallelQuick(a, j+1, hi)
+}
diff --git a/sort/quick.go b/sort/quick.go
index dde71f9..f58f046 100644
--- a/sort/quick.go
+++ b/sort/quick.go
@@ -5,62 +5,55 @@ import (
 )
 
 func Quick(a ds.ArrayList) ds.ArrayList {
-    a = Shuffle(a)
-    quick(a, 0, len(a)-1)
-    return a
+	Shuffle(a)
+	quick(a, 0, len(a)-1)
+	return a
 }
 
 func quick(a ds.ArrayList, lo, hi int) {
-    if hi <= lo {
-        return
-    }
+	if hi <= lo+10 {
+		insertion(a, lo, hi)
+		return
+	}
 
-    j := quickPartition(a, lo, hi)
-    quick(a, lo, j-1)
-    quick(a, j+1, hi)
+	j := quickPartition(a, lo, hi)
+
+	quick(a, lo, j-1)
+	quick(a, j+1, hi)
 }
 
 func quickPartition(a ds.ArrayList, lo, hi int) int {
-    i := lo // Left scan index
-    j := hi+1 // Right scan index
-    v := a[lo] // Partitioning item
-
-    for {
-        // Scan left
-        for {
-            i++
-            if i == hi {
-                break
-            }
-            if a[i].Lower(v) {
-                continue
-            }
-            break
-        }
-
-        // Scan right
-        for {
-            j--
-            if j == lo {
-                break
-            }
-            if v.Lower(a[j]) {
-                continue
-            }
-            break
-        }
-
-        // Check scan complete
-        if i >= j {
-            break
-        }
-
-        a.Swap(i, j)
-    }
-
-    // Put partitioning item v into a[j]
-    a.Swap(lo, j)
-
-    // whith a[lo..j-1 <= a[j] <= a[j+1..hi]
-    return j
+	i := lo     // Left scan index
+	j := hi + 1 // Right scan index
+
+	insertion(a, lo, lo+2)
+	a.Swap(lo, lo+1)
+	v := a[lo] // Partitioning item
+
+	for {
+		for i++; a[i].Lower(v); i++ {
+			if i == hi {
+				break
+			}
+		}
+
+		for j--; v.Lower(a[j]); j-- {
+			if j == lo {
+				break
+			}
+		}
+
+		// Check scan complete
+		if i >= j {
+			break
+		}
+
+		a.Swap(i, j)
+	}
+
+	// Put partitioning item v into a[j]
+	a.Swap(lo, j)
+
+	// whith a[lo..j-1 <= a[j] <= a[j+1..hi]
+	return j
 }
diff --git a/sort/quick2.go b/sort/quick2.go
deleted file mode 100644
index 688e410..0000000
--- a/sort/quick2.go
+++ /dev/null
@@ -1,43 +0,0 @@
-package sort
-
-import (
-	"algorithms/ds"
-)
-
-// Quick2 uses a 3-way partitioning so it is more efficient
-// dealing with duplicates
-func Quick2(a ds.ArrayList) ds.ArrayList {
-	a = Shuffle(a)
-	quick2(a, 0, len(a)-1)
-	return a
-}
-
-func quick2(a ds.ArrayList, lo, hi int) {
-	if hi <= lo {
-		return
-	}
-
-	lt := lo    // Lower than
-	i := lo + 1 // lt..i contain duplicates
-	gt := hi    // Greater than
-	v := a[lo]  // Partitioning item
-
-	for i <= gt {
-		switch a[i].Compare(v) {
-		case -1:
-			a.Swap(lt, i)
-			lt++
-			i++
-		case 1:
-			a.Swap(i, gt)
-			gt--
-		default:
-			// Duplicate
-			i++
-		}
-	}
-	// Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
-
-	quick2(a, lo, lt-1)
-	quick2(a, gt+1, hi)
-}
diff --git a/sort/quick3way.go b/sort/quick3way.go
new file mode 100644
index 0000000..e55b60f
--- /dev/null
+++ b/sort/quick3way.go
@@ -0,0 +1,46 @@
+package sort
+
+import (
+	"algorithms/ds"
+)
+
+// Quick3Way uses a 3-way partitioning so it is more efficient dealing with duplicates
+func Quick3Way(a ds.ArrayList) ds.ArrayList {
+	Shuffle(a)
+	quick3Way(a, 0, len(a)-1)
+	return a
+}
+
+func quick3Way(a ds.ArrayList, lo, hi int) {
+	if hi <= lo+10 {
+		insertion(a, lo, hi)
+		return
+	}
+
+	lt := lo    // Lower than
+	i := lo + 1 // lt..i contain duplicates
+	gt := hi    // Greater than
+
+	insertion(a, lo, lo+2)
+	a.Swap(lo, lo+1)
+	v := a[lo] // Partitioning item
+
+	for i <= gt {
+		switch a[i].Compare(v) {
+		case -1:
+			a.Swap(lt, i)
+			lt++
+			i++
+		case 1:
+			a.Swap(i, gt)
+			gt--
+		default:
+			// Duplicate
+			i++
+		}
+	}
+	// Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
+
+	quick3Way(a, lo, lt-1)
+	quick3Way(a, gt+1, hi)
+}
diff --git a/sort/selection.go b/sort/selection.go
index 3a5774f..66d221e 100644
--- a/sort/selection.go
+++ b/sort/selection.go
@@ -6,6 +6,7 @@ import (
 
 func Selection(a ds.ArrayList) ds.ArrayList {
 	length := len(a)
+
 	for i := 0; i < length; i++ {
 		min := i
 		for j := i + 1; j < length; j++ {
@@ -20,5 +21,6 @@ func Selection(a ds.ArrayList) ds.ArrayList {
 		a[i] = a[min]
 		a[min] = tmp
 	}
+
 	return a
 }
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
 }