5,337
edits
Parallel Algorithms: Difference between revisions
→Technique: Merge Sorting Cluster
No edit summary |
|||
| Line 100: | Line 100: | ||
==Technique: Merge Sorting Cluster== | ==Technique: Merge Sorting Cluster== | ||
===Technique: Partitioning=== | ===Technique: Partitioning=== | ||
Merging: Given two sorted arrays, A and B, create a sorted array C consisting of elements in A and B<br> | |||
* | Ranking: Given an element x, find Rank(x, A) = i such that <math>A(i) \leq x \leq A(i+1)</math><br> | ||
* | |||
;Equivalence of Merging and Ranking | |||
* Given an algorithm for merging, we know A(i) belongs in C(j) so Rank(A(i), B) = j-i | |||
* Given an algorithm for ranking, we get A(i) belongs in C(j) where j = Rank(A(i), B) + i | |||
===Techinque: Divide and Conquer=== | ===Techinque: Divide and Conquer=== | ||