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
Permission is granted to copy and distribute this material for educational purposes only, provided that the following credit line is included: "Concurrent Programming using Java, Copyright 1997 Stephen J. Hartley." Permission is granted to alter and distribute this material provided that the following credit line is included: "Adapted from Concurrent Programming using Java, Copyright 1997 Stephen J. Hartley.