TheAlgorithms-Python

1
"""
2
This is an implementation of odd-even transposition sort.
3

4
It works by performing a series of parallel swaps between odd and even pairs of
5
variables in the list.
6

7
This implementation represents each variable in the list with a process and
8
each process communicates with its neighboring processes in the list to perform
9
comparisons.
10
They are synchronized with locks and message passing but other forms of
11
synchronization could be used.
12
"""
13

14
from multiprocessing import Lock, Pipe, Process
15

16
# lock used to ensure that two processes do not access a pipe at the same time
17
# NOTE This breaks testing on build runner. May work better locally
18
# process_lock = Lock()
19

20
"""
21
The function run by the processes that sorts the list
22

23
position = the position in the list the process represents, used to know which
24
            neighbor we pass our value to
25
value = the initial value at list[position]
26
LSend, RSend = the pipes we use to send to our left and right neighbors
27
LRcv, RRcv = the pipes we use to receive from our left and right neighbors
28
resultPipe = the pipe used to send results back to main
29
"""
30

31

32
def oe_process(position, value, l_send, r_send, lr_cv, rr_cv, result_pipe):
33
    process_lock = Lock()
34

35
    # we perform n swaps since after n swaps we know we are sorted
36
    # we *could* stop early if we are sorted already, but it takes as long to
37
    # find out we are sorted as it does to sort the list with this algorithm
38
    for i in range(10):
39
        if (i + position) % 2 == 0 and r_send is not None:
40
            # send your value to your right neighbor
41
            process_lock.acquire()
42
            r_send[1].send(value)
43
            process_lock.release()
44

45
            # receive your right neighbor's value
46
            process_lock.acquire()
47
            temp = rr_cv[0].recv()
48
            process_lock.release()
49

50
            # take the lower value since you are on the left
51
            value = min(value, temp)
52
        elif (i + position) % 2 != 0 and l_send is not None:
53
            # send your value to your left neighbor
54
            process_lock.acquire()
55
            l_send[1].send(value)
56
            process_lock.release()
57

58
            # receive your left neighbor's value
59
            process_lock.acquire()
60
            temp = lr_cv[0].recv()
61
            process_lock.release()
62

63
            # take the higher value since you are on the right
64
            value = max(value, temp)
65
    # after all swaps are performed, send the values back to main
66
    result_pipe[1].send(value)
67

68

69
"""
70
the function which creates the processes that perform the parallel swaps
71

72
arr = the list to be sorted
73
"""
74

75

76
def odd_even_transposition(arr):
77
    """
78
    >>> odd_even_transposition(list(range(10)[::-1])) == sorted(list(range(10)[::-1]))
79
    True
80
    >>> odd_even_transposition(["a", "x", "c"]) == sorted(["x", "a", "c"])
81
    True
82
    >>> odd_even_transposition([1.9, 42.0, 2.8]) == sorted([1.9, 42.0, 2.8])
83
    True
84
    >>> odd_even_transposition([False, True, False]) == sorted([False, False, True])
85
    True
86
    >>> odd_even_transposition([1, 32.0, 9]) == sorted([False, False, True])
87
    False
88
    >>> odd_even_transposition([1, 32.0, 9]) == sorted([1.0, 32, 9.0])
89
    True
90
    >>> unsorted_list = [-442, -98, -554, 266, -491, 985, -53, -529, 82, -429]
91
    >>> odd_even_transposition(unsorted_list) == sorted(unsorted_list)
92
    True
93
    >>> unsorted_list = [-442, -98, -554, 266, -491, 985, -53, -529, 82, -429]
94
    >>> odd_even_transposition(unsorted_list) == sorted(unsorted_list + [1])
95
    False
96
    """
97
    process_array_ = []
98
    result_pipe = []
99
    # initialize the list of pipes where the values will be retrieved
100
    for _ in arr:
101
        result_pipe.append(Pipe())
102
    # creates the processes
103
    # the first and last process only have one neighbor so they are made outside
104
    # of the loop
105
    temp_rs = Pipe()
106
    temp_rr = Pipe()
107
    process_array_.append(
108
        Process(
109
            target=oe_process,
110
            args=(0, arr[0], None, temp_rs, None, temp_rr, result_pipe[0]),
111
        )
112
    )
113
    temp_lr = temp_rs
114
    temp_ls = temp_rr
115

116
    for i in range(1, len(arr) - 1):
117
        temp_rs = Pipe()
118
        temp_rr = Pipe()
119
        process_array_.append(
120
            Process(
121
                target=oe_process,
122
                args=(i, arr[i], temp_ls, temp_rs, temp_lr, temp_rr, result_pipe[i]),
123
            )
124
        )
125
        temp_lr = temp_rs
126
        temp_ls = temp_rr
127

128
    process_array_.append(
129
        Process(
130
            target=oe_process,
131
            args=(
132
                len(arr) - 1,
133
                arr[len(arr) - 1],
134
                temp_ls,
135
                None,
136
                temp_lr,
137
                None,
138
                result_pipe[len(arr) - 1],
139
            ),
140
        )
141
    )
142

143
    # start the processes
144
    for p in process_array_:
145
        p.start()
146

147
    # wait for the processes to end and write their values to the list
148
    for p in range(len(result_pipe)):
149
        arr[p] = result_pipe[p][0].recv()
150
        process_array_[p].join()
151
    return arr
152

153

154
# creates a reverse sorted list and sorts it
155
def main():
156
    arr = list(range(10, 0, -1))
157
    print("Initial List")
158
    print(*arr)
159
    arr = odd_even_transposition(arr)
160
    print("Sorted List\n")
161
    print(*arr)
162

163

164
if __name__ == "__main__":
165
    main()
166