If you have one huge amount of numbers and one hundred computers, How would you find the median of the numbers?
+12
A:
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 from 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 algo) and that will be the leader
read the wiki article - http://en.wikipedia.org/wiki/Selection_algorithm
MrOhad
2010-07-23 08:13:12
+1, but I think you meant to say ["selection algorithm"](http://en.wikipedia.org/wiki/Selection_algorithm), not selection sort.
interjay
2010-07-24 21:26:45
correct, I'll fix that...thanks!
MrOhad
2010-07-24 21:37:09