Lab 21: Parallelization
- It's typically thought that it takes at least O(NlogN) time to
sort an array.
- However, if you do it in parallel, you can do it in N time.
- The algorithm is that each process is connected to both its neighbors
(except the end ones).
- In alternating steps each process looks right then left (lets' say
the odds start with right and the evens with left).
- If the left is larger than the right, switch.
- This will sort in N time. (Though there still O(NlogN) switches).
- Implement this. You are welcome to do it how you like, but I suggest
- Put in an unsorted array of say 10 numbers.
- Write a print function to print the array.
- Now, simulate processes by calling a function with the two
- Implement a pass function between two adjacent processes.
- Loop through 10 times calling the processes, and printing
out the array.
- If you've got this far, make it work for 100 numbers
with randomly initialised numbers.
- If you've got this far, actually fork off processes.