5,350
edits
Parallel Algorithms: Difference between revisions
→Integer Sorting
| Line 191: | Line 191: | ||
Assume n is divisible by r (<math>r=\sqrt{n}</math>) | 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> | * Partition A into n/r subarrays <math>B_1,...,B_{n/r}</math> | ||
** Sort each subarray separately using serial bucket sort (counting sort) | ** Sort each subarray separately using serial bucket sort (counting sort) | ||
| Line 200: | Line 200: | ||
* The rank of element <math>i</math> is <math>1+serial(i)+ps(v,s-1)+global_ps(v-1)</math> | * The rank of element <math>i</math> is <math>1+serial(i)+ps(v,s-1)+global_ps(v-1)</math> | ||
===Complexity=== | |||
* Step 1:<math>T=O(r),\;W=O(r)</math> per subarray. | * Step 1:<math>T=O(r),\;W=O(r)</math> per subarray. | ||
** Total: <math>T=O(r),\; W=O(n)</math> | ** Total: <math>T=O(r),\; W=O(n)</math> | ||
| Line 208: | Line 208: | ||
* Step 4: <math>T=O(1)\; W=O(n)</math> | * Step 4: <math>T=O(1)\; W=O(n)</math> | ||
* Total: <math>T=O(r + \log n),\; W=O(n)</math> | * Total: <math>T=O(r + \log n),\; W=O(n)</math> | ||
;Notes | ;Notes | ||
* Running time is not poly-log | * Running time is not poly-log | ||
===Theorems=== | |||
* The integer sorting algorithm runs in <math>O(r+\log n)</math> time and <math>O(n)</math> work | |||
* The integer sorting algorithm can be applied to run in time <math>O(k(r^{1/k}+\log n))</math> and work <math>O(kn)</math> | |||
Radix sort using the basic integer sort (BIS) algorithm. | |||
==Resources== | ==Resources== | ||