5,337
edits
Parallel Algorithms: Difference between revisions
→Integer Sorting
| Line 193: | Line 193: | ||
;Algorithm | ;Algorithm | ||
* Partition A into n/r subarrays <math>B_1,...,B_{n/r}</math> | * Partition A into n/r subarrays <math>B_1,...,B_{n/r}</math> | ||
** Sort each subarray separately using | ** Sort each subarray separately using serial bucket sort | ||
** Compute number(v,s) # of elements of value v in <math>B_s</math> for <math>0\leq v \leq r-1</math> and <math>1 \leq s \leq n/r</math> | ** Compute number(v,s) # of elements of value v in <math>B_s</math> for <math>0\leq v \leq r-1</math> and <math>1 \leq s \leq n/r</math> | ||
** Compute serial(i) = # of elements in the block <math>B_s</math> such that A(j)=A(i) and <math> j < i </math> <math>1 \leq j \neq n</math> | ** Compute serial(i) = # of elements in the block <math>B_s</math> such that A(j)=A(i) and <math> j < i </math> <math>1 \leq j \neq n</math> | ||