merge

1 files changed, 66 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
+}