Parallel bubble sort (shown below) has O(n) complexity.
PARALLEL BUBBLE SORT (A)
For k = 0 to n-2
If k is even then
for i = 0 to (n/2)-1 do in parallel
If A[2i] > A[2i+1] then
Exchange A[2i] ↔ A[2i+1]
Else
for i = 0 to (n/2)-2 do in parallel
If A[2i+1] > A[2i+2] then
Exchange A[2i+1] ↔ A[2i+2]
Next k
After bubble sort is done, you can select 1st k or last k elements of
the array to find k largest/smallest elements.
Please note that the ordinary sequential bubble sort has complexity
O(n*n).
Regards,
Mukul
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
