Prev: Parallel sort
Next: Khoros Visualization image ( .xv format) not recognized in MATLAB!!
From: Khalid Rumman on 7 Apr 2010 20:46
Hi
I'm Beginner at MATLAB and i need to use this algorithm that implements the CRCW PRAM parallel quicksort in my project.
The binary tree construction procedure for the CRCW PRAM parallel quicksort formulation.
1. procedure BUILD TREE (A[1...n])
2. begin
3. for each process i do
4. begin
5. root := i;
6. parenti := root;
7. leftchild[i] := rightchild[i] := n + 1;
8. end for
9. repeat for each process i r oot do
10. begin
11. if (A[i] < A[parenti]) or
(A[i]= A[parenti] and i <parenti) then
12. begin
13. leftchild[parenti] :=i ;
14. if i = leftchild[parenti] then exit
15. else parenti := leftchild[parenti];
16. end for
17. else
18. begin
19. rightchild[parenti] :=i;
20. if i = rightchild[parenti] then exit
21. else parenti := rightchild[parenti];
22. end else
23. end repeat
24. end BUILD_TREE
After building the binary tree, the algorithm determines the position of each element in the sorted array. It traverses the tree and keeps a count of the number of elements in the left and right subtrees of any element. Finally, each element is placed in its proper position in time Q(1), and the array is sorted.

I'll be grateful if any one can help with this.
thanks

From: Walter Roberson on 7 Apr 2010 20:56
Khalid Rumman wrote:

> 1. procedure BUILD TREE (A[1...n]) 2. begin 3. for each process
> i do 4. begin 5. root := i; 6. parenti := root;
> 7. leftchild[i] := rightchild[i] := n + 1; 8. end for
> 9. repeat for each process i r oot do 10. begin 11. if
> (A[i] < A[parenti]) or (A[i]= A[parenti] and i <parenti)
> then 12. begin 13. leftchild[parenti] :=i ;
> 14. if i = leftchild[parenti] then exit 15. else
> parenti := leftchild[parenti]; 16. end for 17. else
> 18. begin 19. rightchild[parenti] :=i; 20. if
> i = rightchild[parenti] then exit 21. else parenti :=
> rightchild[parenti]; 22. end else 23. end repeat 24. end
> BUILD_TREE

Line 16 _appears_ to be incorrect. It is an 'end for', but the only enclosing
repetition loop is the 'repeat' for which there is an explicit 'end repeat'.
From: Khalid Rumman on 8 Apr 2010 10:55
Walter Roberson wrote
> Line 16 _appears_ to be incorrect. It is an 'end for', but the only enclosing
> repetition loop is the 'repeat' for which there is an explicit 'end repeat'.

Thanks for your note, the corrections can be found at :
http://users.atw.hu/parallelcomp/ch09lev1sec4.html
 | 
Pages: 1
Prev: Parallel sort
Next: Khoros Visualization image ( .xv format) not recognized in MATLAB!!