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); } }At the bottom of the animation window is a button and text field showing the default values of some of the command line arguments. Alter these as needed and click the button.
-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