initial quick sort but have to figure out why it is so slow

2 files changed, 78 insertions, 0 deletions

diff --git a/sort/quick.go b/sort/quick.go
new file mode 100644
index 0000000..dde71f9
--- /dev/null
+++ b/sort/quick.go
@@ -0,0 +1,66 @@
+package sort
+
+import (
+	"algorithms/ds"
+)
+
+func Quick(a ds.ArrayList) ds.ArrayList {
+    a = Shuffle(a)
+    quick(a, 0, len(a)-1)
+    return a
+}
+
+func quick(a ds.ArrayList, lo, hi int) {
+    if hi <= lo {
+        return
+    }
+
+    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
+}
diff --git a/sort/sort_test.go b/sort/sort_test.go
index ad75fff..bd9db9b 100644
--- a/sort/sort_test.go
+++ b/sort/sort_test.go
@@ -33,6 +33,12 @@ func TestShellSort(t *testing.T) {
 	}
 }
 
+func TestQuickSort(t *testing.T) {
+	for i := 1; i <= maxLength; i *= 10 {
+		test(Quick, i, t)
+	}
+}
+
 func TestShuffleSort(t *testing.T) {
 	for i := 10; i <= maxLength; i *= 10 {
 		testShuffle(Shuffle, i, t)
@@ -57,6 +63,12 @@ func BenchmarkShellSort(b *testing.B) {
 	}
 }
 
+func BenchmarkQuickSort(b *testing.B) {
+	for i := 1; i <= maxLength; i *= 10 {
+		benchmark(Quick, i, b)
+	}
+}
+
 func BenchmarkShuffleSort(b *testing.B) {
 	for i := 1; i <= maxLength; i *= 10 {
 		benchmark(Shuffle, i, b)