CODEWITHSUNDEEP
algorithmparallel-processing
user399950
user399950

Reputation:

Find a median in parallel

If you have one huge amount of numbers and one hundred computers, How would you find the median of the numbers?

Upvotes: 21

Views: 8385

Answers (1)

DuduAlul
DuduAlul

Reputation: 6390

Use selection algorithm.

  1. Split the array of number to 100 partitions.
  2. Each processor should use the general pivot to split the array to two groups (left/right)
  3. Then each processor should send the size of those 2 groups to the leader
  4. The leader should calculate which group is smaller and broadcast a message to get rid of one of those groups.
  5. Go back to step 2 until you find the median

this solution has an avg runtime of O(n) in order to make it asymptotic runtime of O(n), each processor should split the numbers to groups of 5 elements find the median of each group (using insertion sort) and send those medians back to the leader, the leader will choose the median of those medians (using the same algorithm) and that will be the pivot

read the wiki article - http://en.wikipedia.org/wiki/Selection_algorithm

Upvotes: 21

Related Questions