-
Notifications
You must be signed in to change notification settings - Fork 0
/
quicksort_parallel.py
51 lines (39 loc) · 1.19 KB
/
quicksort_parallel.py
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
42
43
44
45
46
47
48
49
50
51
import random
from multiprocessing import Pipe, Process
from quicksort_sequential import quicksort_sequential
def quicksort_parallel(arr, p_pipe, num_max_proc, num_current_proc):
if len(arr) < 2 or num_current_proc > num_max_proc:
p_pipe.send(quicksort_sequential(arr))
p_pipe.close()
return
pivot = arr.pop(random.randint(0, len(arr) - 1))
left_arr = [item for item in arr if item < pivot]
right_arr = [item for item in arr if item >= pivot]
left_p_pipe, left_c_pipe = Pipe(duplex=False)
right_p_pipe, right_c_pipe = Pipe(duplex=False)
left_proc = Process(
target=quicksort_parallel,
args=(
left_arr,
left_c_pipe,
num_max_proc,
num_current_proc + 1
)
)
right_proc = Process(
target=quicksort_parallel,
args=(
right_arr,
right_c_pipe,
num_max_proc,
num_current_proc + 1
)
)
left_proc.start()
right_proc.start()
p_pipe.send(left_p_pipe.recv() + [pivot] + right_p_pipe.recv())
p_pipe.close()
left_proc.join()
right_proc.join()
left_proc.close()
right_proc.close()