sort/parallelquick.go


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package sort

import (
	"algorithms/ds"
	"sync"
)

func ParallelQuick(a ds.ArrayList) ds.ArrayList {
	Shuffle(a)
	parallelQuick(a)
	return a
}

func parallelQuick(a ds.ArrayList) {
	l := len(a)
	if l <= 10 {
		Insertion(a)
		return
	}

	j := quickPartition(a)

	if l >= 1000 {
		var wg sync.WaitGroup
		wg.Add(2)
		defer wg.Wait()

		go func() {
			parallelQuick(a[0:j])
			wg.Done()
		}()
		go func() {
			parallelQuick(a[j+1:])
			wg.Done()
		}()
		return
	}

	parallelQuick(a[0:j])
	parallelQuick(a[j+1:])
}