This is an animation of the parallel quick sort algorithm. There are six CPUs available and one initial partition of random positive numbers to sort. The left-most circle is chosen as the pivot point of the partition. The circles less than the pivot are swept to the lower left quadrant of the partition and the circles larger than the pivot are swept to the upper right quadrant of the partition. Then the pivot circle is moved to the middle of the partition and changed to solid black. This leaves two new partitions to which the algorithm is applied recursively by any two available CPUs. The circles in a partition take on the solid color of the CPU working on them except the pivot which is outline.

private static void quickSort(int worker
int left
int right) {
   int pivot = nums[left]; int l = left
r = right;
   // enclose what this worker is working on in a black outline rectangle
   int ymin = minn(nums
left
right);
   int ymax = maxx(nums
left
right);
   float xpos
ypos
xsize
ysize;
   xpos = scaleX(left); ypos = scaleY(ymin);
   xsize = scaleX(right-left); ysize = scaleY(ymax-ymin);
   xa.rectangle("rect"+worker
xpos
ypos
xsize
ysize
Color.black
xa.OUTLINE);
   xa.delay(1);
   // change items sorted to this worker's color
   for (int i = left; i <= right; i++) {
      xa.color("nums"+i
colors[worker]);   // would be better to do
      xa.fill("nums"+i
xa.SOLID);          // these as a batch i.e.
   }                                        // no frameDelay
   xa.delay(1);
   // make pivot outline color
   xa.fill("nums"+left
xa.OUTLINE);
   // draw a black horizontal line from the pivot across the rectangle
   xpos = scaleX(left); ypos = scaleY(pivot);
   xsize = scaleX(right-left); ysize = 0.0f;
   xa.line("lineH"+worker
xpos
ypos
xsize
ysize
Color.black
xa.THIN);
   // draw two vertical lines at left+1 and right
   xpos = scaleX(l+1); ypos = scaleY(pivot);
   xsize = 0.0f; ysize = scaleY(ymax-pivot);
   xa.line("lineVL"+worker
xpos
ypos
xsize
ysize
Color.black
xa.THIN);
   xpos = scaleX(r); ypos = scaleY(ymin);
   xsize = 0.0f; ysize = scaleY(pivot-ymin);
   xa.line("lineVR"+worker
xpos
ypos
xsize
ysize
Color.black
xa.THIN);
   xa.delay(1);
   boolean done = false;
   while (!done) {
      if (nums[l+1] > pivot) {
         while (r > l+1 && nums[r] > pivot) { r--;
            // move the right vertical line one to the left
            if (!done) {
               xa.jumpRelative("lineVR"+worker
scaleX(-1)
0.0f);
            }
         }
         if (r > l+1) { l++;
            int temp = nums[r]; nums[r] = nums[l]; nums[l] = temp;
            done = l >= r-1;
            // swap locations and ids of the objects
            xa.moveAsync("nums"+r
scaleX(l)
scaleY(nums[l]));
            xa.move("nums"+l
scaleX(r)
scaleY(nums[r]));
            xa.swapIds("nums"+r
nums
+l);
            // move the left vertical line one to the right
            if (!done) {
               xa.jumpRelative("lineVL"+worker
scaleX(1)
0.0f);
            }
         } else done = true;
      } else { l++; done = l >= r;
         // move the left vertical line one to the right
         if (!done) {
            xa.jumpRelative("lineVL"+worker
scaleX(1)
0.0f);
         }
      }
   }
   int temp = nums[left]; nums[left] = nums[l]; nums[l] = temp;
   // swap locations and ids of the objects
   xa.moveAsync("nums"+left
scaleX(l)
scaleY(nums[l]));
   xa.move("nums"+l
scaleX(left)
scaleY(nums[left]));
   xa.swapIds("nums"+left
nums
+l);
   if (right-(l+1) > 0) send(task
new Task(l+1
right));
   else if (right-(l+1) == 0) {  V(doneCount);
      // color the object solid black to indicate it is in final position
      xa.color("nums"+right
Color.black);
      xa.fill("nums"+right
xa.SOLID);
   }
   // delete the line and rectangle objects
   xa.delete("rect"+worker);
   xa.delete("lineH"+worker);
   xa.delete("lineVL"+worker);
   xa.delete("lineVR"+worker);
   V(doneCount);
   // color the object solid black to indicate it is in final position
   xa.color("nums"+l
Color.black);
   xa.fill("nums"+l
xa.SOLID);
   if ((l-1)-left > 0) send(task
new Task(left
l-1));
   else if ((l-1)-left == 0) {  V(doneCount);
      // color the object solid black to indicate it is in final position
      xa.color("nums"+left
Color.black);
      xa.fill("nums"+left
xa.SOLID);
   }
}

-n: number of numbers to sort
-r: range of random numbers generated to sort (from 1)
-p: number of CPUs (worker threads) available

© 1998 Stephen J. Hartley