add parallelquick and so on

1 files changed, 40 insertions, 0 deletions

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)
+}