From 390333bb314f6cb25adc5716ea383112860ed342 Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Sat, 8 Aug 2020 13:01:36 +0100 Subject: add parallelquick and so on --- sort/parallelquick.go | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 sort/parallelquick.go (limited to 'sort/parallelquick.go') 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) +} -- cgit v1.2.3