modify global
partition(start, end) = {
local pivot, bottom, top, done;
// Partition around the last value
pivot := self.quicksortlist[end];
// Start outside the area to be partitioned
bottom := start-1;
top := end;
done := nil;
// Until all elements are partitioned...
while (!done) {
// Until we find an out of place element...
while (!done) {
// ... move the bottom up.
bottom ++;
// If we hit the top...
if (bottom = top) {
// ... we are done.
done := true;
break;
}
// Is the bottom out of place?
if (self.quicksortlist[bottom] > pivot) {
// Then put it at the top...
self.quicksortlist[top] := self.quicksortlist[bottom];
// ... and start searching from the top.
break;
}
}
// Until we find an out of place element...
while (!done) {
// ... move the top down.
top := top-1;
// If we hit the bottom...
if (top = bottom) {
// ... we are done.
done := true;
break;
}
// Is the top out of place?
if (self.quicksortlist[top] < pivot) {
// Then put it at the bottom...
self.quicksortlist[bottom] := self.quicksortlist[top];
// ...and start searching from the bottom.
break;
}
}
}
// Put the pivot in its place.
self.quicksortlist[top] := pivot;
// Return the split point
return top;
}
subquicksort(start, end) = {
local split;
// If there are two or more elements...
if (start < end) {
// ... partition the sublist...
split := self.partition(start, end);
// ... and sort both halves.
self.subquicksort(start, split-1);
self.subquicksort(split+1, end);
} else {
return;
}
}
doquicksort() = {
self.subquicksort(1, length(self.quicksortlist));
}
;
