5,337
edits
Parallel Algorithms: Difference between revisions
→Integer Sorting
| Line 188: | Line 188: | ||
Input: Array A[1..n], integers are range [0..r-1]<br> | Input: Array A[1..n], integers are range [0..r-1]<br> | ||
Sorting: rank from smallest to largest<br> | |||
Assume n is divisible by r (<math>r=\sqrt{n}</math>) | |||
;Algorithm | |||
* Partition A into n/r subarrays <math>B_1,...,B_{n/r}</math> | |||
** Sort each subarray separately using counting 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 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> | |||
* Run prefix sum on number(v,1),number(v,2),...,number(v,n/r) into ps(v,1), ps(v,2),..., ps(v,n/r) | |||
* Compute prefix sums of cardinality(0),.., cardinality(r-1) into global_ps(0),...,global_ps(r-1) | |||
* The rank of element <math>i</math> is <math>1+serial(i)+ps(v,s-1)+global_ps(v-1)</math> | |||
;Notes | |||
* Running time is not poly-log | |||
==Resources== | ==Resources== | ||