refactor quicksort

5 files changed, 43 insertions, 51 deletions

diff --git a/sort/insertion.go b/sort/insertion.go
index 6663bca..203d4f2 100644
--- a/sort/insertion.go
+++ b/sort/insertion.go
@@ -5,12 +5,7 @@ import (
 )
 
 func Insertion(a ds.ArrayList) ds.ArrayList {
-	insertion(a, 0, len(a)-1)
-	return a
-}
-
-func insertion(a ds.ArrayList, lo, hi int) {
-	for i := lo; i <= hi; i++ {
+	for i, _ := range a {
 		for j := i; j > 0; j-- {
 			if a[j] > a[j-1] {
 				break
@@ -18,4 +13,6 @@ func insertion(a ds.ArrayList, lo, hi int) {
 			a.Swap(j, j-1)
 		}
 	}
+
+	return a
 }
diff --git a/sort/parallelquick.go b/sort/parallelquick.go
index f68135f..2ac9f0e 100644
--- a/sort/parallelquick.go
+++ b/sort/parallelquick.go
@@ -7,34 +7,35 @@ import (
 
 func ParallelQuick(a ds.ArrayList) ds.ArrayList {
 	Shuffle(a)
-	parallelQuick(a, 0, len(a)-1)
+	parallelQuick(a)
 	return a
 }
 
-func parallelQuick(a ds.ArrayList, lo, hi int) {
-	if hi <= lo+10 {
-		insertion(a, lo, hi)
+func parallelQuick(a ds.ArrayList) {
+	length := len(a)
+	if length <= 10 {
+		Insertion(a)
 		return
 	}
 
-	j := quickPartition(a, lo, hi)
+	j := quickPartition(a)
 
-	if hi <= lo+1000 {
+	if length >= 1000 {
 		var wg sync.WaitGroup
 		wg.Add(2)
 		defer wg.Wait()
 
 		go func() {
-			parallelQuick(a, lo, j-1)
+			parallelQuick(a[0:j])
 			wg.Done()
 		}()
 		go func() {
-			parallelQuick(a, j+1, hi)
+			parallelQuick(a[j+1:])
 			wg.Done()
 		}()
 		return
 	}
 
-	parallelQuick(a, lo, j-1)
-	parallelQuick(a, j+1, hi)
+	parallelQuick(a[0:j])
+	parallelQuick(a[j+1:])
 }
diff --git a/sort/quick.go b/sort/quick.go
index 5dbcfe5..72db370 100644
--- a/sort/quick.go
+++ b/sort/quick.go
@@ -6,41 +6,34 @@ import (
 
 func Quick(a ds.ArrayList) ds.ArrayList {
 	Shuffle(a)
-	quick(a, 0, len(a)-1)
+	quick(a)
 	return a
 }
 
-func quick(a ds.ArrayList, lo, hi int) {
-	if hi <= lo+10 {
-		insertion(a, lo, hi)
+func quick(a ds.ArrayList) {
+	if len(a) <= 10 {
+		Insertion(a)
 		return
 	}
 
-	j := quickPartition(a, lo, hi)
-
-	quick(a, lo, j-1)
-	quick(a, j+1, hi)
+	j := quickPartition(a)
+	quick(a[0:j])
+	quick(a[j+1:])
 }
 
-func quickPartition(a ds.ArrayList, lo, hi int) int {
-	i := lo     // Left scan index
-	j := hi + 1 // Right scan index
+func quickPartition(a ds.ArrayList) int {
+	i := 0      // Left scan index
+	j := len(a) // Right scan index
 
-	insertion(a, lo, lo+2)
-	a.Swap(lo, lo+1)
-	v := a[lo] // Partitioning item
+	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 j--; v < a[j]; j-- {
-			if j == lo {
-				break
-			}
 		}
 
 		// Check scan complete
@@ -52,7 +45,7 @@ func quickPartition(a ds.ArrayList, lo, hi int) int {
 	}
 
 	// Put partitioning item v into a[j]
-	a.Swap(lo, j)
+	a.Swap(0, j)
 
 	// whith a[lo..j-1 <= a[j] <= a[j+1..hi]
 	return j
diff --git a/sort/quick3way.go b/sort/quick3way.go
index e6cb677..6e7dc18 100644
--- a/sort/quick3way.go
+++ b/sort/quick3way.go
@@ -7,23 +7,24 @@ import (
 // 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)
+	quick3Way(a)
 	return a
 }
 
-func quick3Way(a ds.ArrayList, lo, hi int) {
-	if hi <= lo+10 {
-		insertion(a, lo, hi)
+func quick3Way(a ds.ArrayList) {
+	length := len(a)
+	if length <= 10 {
+		Insertion(a)
 		return
 	}
 
-	lt := lo    // Lower than
-	i := lo + 1 // lt..i contain duplicates
-	gt := hi    // Greater than
+	lt := 0          // Lower than
+	i := 1           // lt..i contain duplicates
+	gt := length - 1 // Greater than
 
-	insertion(a, lo, lo+2)
-	a.Swap(lo, lo+1)
-	v := a[lo] // Partitioning item
+	Insertion(a[0:3])
+	a.Swap(0, 1)
+	v := a[0] // Partitioning item
 
 	for i <= gt {
 		switch {
@@ -41,6 +42,6 @@ func quick3Way(a ds.ArrayList, lo, hi int) {
 	}
 	// Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
 
-	quick3Way(a, lo, lt-1)
-	quick3Way(a, gt+1, hi)
+	quick3Way(a[0:lt])
+	quick3Way(a[gt+1:])
 }
diff --git a/sort/sort_test.go b/sort/sort_test.go
index 6f6bcc2..f350b46 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -11,8 +11,8 @@ var benchResult ds.ArrayList
 var benchResultInt []int
 
 const minLength int = 1
-const maxLength int = 100000
-const maxSlowLength int = 100000
+const maxLength int = 1000
+const maxSlowLength int = 1000
 
 var arrayListCache map[string]ds.ArrayList