Figure 3
A quicksort function in DAPPLE.
<![CDATA[
void quicksort(intVector& X) // the sort is done in place, ie, X is updated
{
// check the number of active processors (ie, size of our sublist)
int n = n_active(X); // how big is this sublist?
if (n <= 1) ; // do nothing
else if (n == 2) { // possibly swap them
int largest = max_value(X);
int smallest = min_value(X);
ifp (VP == first(VP))
X = smallest; // first one get smallest
else
X = largest; // second one gets largest
} else { // n >= 3
intVector P(N); // permutation vector
const intVector ONE(N,1); // constant vector of all 1s
int splitter; // splitter value
int left, middle, right; // first VP# in each subset
// pick a splitter; I'll just use the first value
splitter = first(X);
left = first_index(X); // which VP holds the splitter?
// find the left half, those less than or equal to splitter
// (except for that first one)...
ifp (X <= splitter && VP != left) {
// compute our destination in the result vector
P = left + plus_scan(ONE); // i.e., left, left+1, left+2...
middle = left + n_active(X); // the rest will begin here
}
// move the splitter into the middle
ifp (VP == left) {
P = middle; // route it there later
right = middle + 1; // the rest will begin here
}
// do the right half, those greater than the splitter
ifp (X > splitter) {
// compute our destination in the result vector
P = right + plus_scan(ONE); // i.e., right, right+1, right+2...
}
X = permute(X, P); // partition the data
ifp (VP < middle)
quicksort(X); // sort the left half
ifp (VP > middle)
quicksort(X); // sort the right half
}
}
]]>