|
| 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 | +frommultiprocessingimportProcess,Pipe,Lock |
| 14 | + |
| 15 | +#lock used to ensure that two processes do not access a pipe at the same time |
| 16 | +processLock=Lock() |
| 17 | + |
| 18 | +""" |
| 19 | +The function run by the processes that sorts the list |
| 20 | +
|
| 21 | +position = the position in the list the prcoess represents, used to know which |
| 22 | + neighbor we pass our value to |
| 23 | +value = the initial value at list[position] |
| 24 | +LSend, RSend = the pipes we use to send to our left and right neighbors |
| 25 | +LRcv, RRcv = the pipes we use to receive from our left and right neighbors |
| 26 | +resultPipe = the pipe used to send results back to main |
| 27 | +""" |
| 28 | +defoeProcess(position,value,LSend,RSend,LRcv,RRcv,resultPipe): |
| 29 | +globalprocessLock |
| 30 | + |
| 31 | +#we perform n swaps since after n swaps we know we are sorted |
| 32 | +#we *could* stop early if we are sorted already, but it takes as long to |
| 33 | +#find out we are sorted as it does to sort the list with this algorithm |
| 34 | +foriinrange(0,10): |
| 35 | + |
| 36 | +if( (i+position)%2==0andRSend!=None): |
| 37 | +#send your value to your right neighbor |
| 38 | +processLock.acquire() |
| 39 | +RSend[1].send(value) |
| 40 | +processLock.release() |
| 41 | + |
| 42 | +#receive your right neighbor's value |
| 43 | +processLock.acquire() |
| 44 | +temp=RRcv[0].recv() |
| 45 | +processLock.release() |
| 46 | + |
| 47 | +#take the lower value since you are on the left |
| 48 | +value=min(value,temp) |
| 49 | +elif( (i+position)%2!=0andLSend!=None): |
| 50 | +#send your value to your left neighbor |
| 51 | +processLock.acquire() |
| 52 | +LSend[1].send(value) |
| 53 | +processLock.release() |
| 54 | + |
| 55 | +#receive your left neighbor's value |
| 56 | +processLock.acquire() |
| 57 | +temp=LRcv[0].recv() |
| 58 | +processLock.release() |
| 59 | + |
| 60 | +#take the higher value since you are on the right |
| 61 | +value=max(value,temp) |
| 62 | +#after all swaps are performed, send the values back to main |
| 63 | +resultPipe[1].send(value) |
| 64 | + |
| 65 | +""" |
| 66 | +the function which creates the processes that perform the parallel swaps |
| 67 | +
|
| 68 | +arr = the list to be sorted |
| 69 | +""" |
| 70 | +defOddEvenTransposition(arr): |
| 71 | + |
| 72 | +processArray= [] |
| 73 | +tempRrcv=None |
| 74 | +tempLrcv=None |
| 75 | + |
| 76 | +resultPipe= [] |
| 77 | + |
| 78 | +#initialize the list of pipes where the values will be retrieved |
| 79 | +forainarr: |
| 80 | +resultPipe.append(Pipe()) |
| 81 | + |
| 82 | +#creates the processes |
| 83 | +#the first and last process only have one neighbor so they are made outside |
| 84 | +#of the loop |
| 85 | +tempRs=Pipe() |
| 86 | +tempRr=Pipe() |
| 87 | +processArray.append(Process(target=oeProcess,args= (0,arr[0],None,tempRs,None,tempRr,resultPipe[0]))) |
| 88 | +tempLr=tempRs |
| 89 | +tempLs=tempRr |
| 90 | + |
| 91 | +foriinrange(1,len(arr)-1): |
| 92 | +tempRs=Pipe() |
| 93 | +tempRr=Pipe() |
| 94 | +processArray.append(Process(target=oeProcess,args= (i,arr[i],tempLs,tempRs,tempLr,tempRr,resultPipe[i]))) |
| 95 | +tempLr=tempRs |
| 96 | +tempLs=tempRr |
| 97 | + |
| 98 | +processArray.append(Process(target=oeProcess,args= (len(arr)-1,arr[len(arr)-1],tempLs,None,tempLr,None,resultPipe[len(arr)-1]))) |
| 99 | + |
| 100 | +#start the processes |
| 101 | +forpinprocessArray: |
| 102 | +p.start() |
| 103 | + |
| 104 | +#wait for the processes to end and write their values to the list |
| 105 | +forpinrange(0,len(resultPipe)): |
| 106 | +arr[p]=resultPipe[p][0].recv() |
| 107 | +processArray[p].join() |
| 108 | + |
| 109 | +return(arr) |
| 110 | + |
| 111 | + |
| 112 | +#creates a reverse sorted list and sorts it |
| 113 | +defmain(): |
| 114 | +arr= [] |
| 115 | + |
| 116 | +foriinrange(10,0,-1): |
| 117 | +arr.append(i) |
| 118 | +print("Initial List") |
| 119 | +print(*arr) |
| 120 | + |
| 121 | +list=OddEvenTransposition(arr) |
| 122 | + |
| 123 | +print("Sorted List\n") |
| 124 | +print(*arr) |
| 125 | + |
| 126 | +if__name__=="__main__": |
| 127 | +main() |