Shaker's sequential sorting algorithm is clear. But what about parallel? It is not clear that they must carry out each of the processor elements and what data should they pass to them?

Push, please, on a thought.

  • And who ever said that it is possible to parallelize any algorithm? This is basically impossible. Here you can use algorithms that initially have a massively parallel nature. Type the same sort of merge. - gecube
  • @gecube, this is a learning task. You need to parallelize this sorting. How effective it is is another question. - Gercules
  • Look at how they parallel themselves: sorting Kwik, sorting Bubble and other wonderful people - Dith


1 answer 1

Well, the first thing that comes to mind is to break the array into parts and feed them to different streams. Results from the streams to analyze (find among all the minimum and maximum element). Next, send the arrays without the found minimum and maximum elements again to these threads, analyze the results. And so on ...

  • Those. at each step 2 elements fall into place: the maximum and minimum? For some reason, in my thoughts it was - at every step there should be 2 * number of elements in its place, but a lot of “buts” came out. - Gercules
  • Sort by the specified algorithm 2 halves of the array and perform their merging. This is enough for training purposes - renegator