6.7 Algorithm Visualization
Sorting algorithms are especially amenable to pictorial representations that make plain their dynamic characteristics. We have already seen, in figures throughout this chapter, several examples that illustrate this point. Visual representations are both so useful in understanding the operation sorting algorithms and so easy to create, that we digress briefly to discuss the topic.
Perhaps the simplest way to create visualizations of sorting algorithms is to use PostScript (see Section 4.3), as illustrated in Figure 6.9. Little could be more straightforward than to plot an array of points, given their coordinates. Similarly, implementing a Java program that creates PostScript programs like this is not much more difficult than implementing one that prints out the contents of the array periodically, as shown in Program 6.15.
Figure 6.9. PostScript visualization of array contents
This PostScript program plots the contents of an array of numbers between 0 and 1 by calling the function dot, with the index and value of each array entry as arguments. The values w and h are the width and height of the frame, respectively, and N is the number of values in the array. The dot function scales the index to be an x coordinate between 0 and w by multiplying by w and dividing by N, and the value to be a y coordinate between 0 and h by multiplying by h. It then draws a filled circle of radius 2 at (x,y).
Of course, Java also has a Graphics object with associated drawing methods, and we might simply use those directly for creating a visualization (see Exercise 6.42). We leave that for an exercise because in Java it is more interesting and not much more difficult to consider dynamic visual respresentations, where we can watch the items move through the array as it is sorted.
Programs 6.16 and 6.17 implement a sample Java sorting animation in a Java applet. The implementation is based on instrumenting the exch method to change the visual representation every time the sorting algorithm does an exchange.
Program 6.15 Visualizing a sorting algorithm
This program prints out a PostScript program like the one in Figure 6.9. The constants h and w give the height and width (respectively) of the frames (in points), and the constant cuts gives the number of frames. The show method prints the code that plots the values in the array, and the sort is instrumented to call show at appropriate intervals.
class Visualize { private static final int cuts = 5, h = 72, w = 72; static int N; static void sort(double a[], int l, int r) { double t; for (int i = l; i <= r; i++) { for (int j = i; j > l; j--) if (a[j] < a[j-1]) exch(a, j-1, j); if (i*cuts % N == 0) show(a, l, r); } } static void show(double[] a, int l, int r) { for (int i = l; i <= r; i++) { float x = h*((float) i) / ((float) N); float y = w*((float) a[i]); Out.println(x + " " + y + " dot"); } Out.println(1.1*w + " 0 translate"); } public static void main(String[] args) { N = Integer.parseInt(args[0]); double a[] = new double[N]; for (int i = 0; i < N; i++) a[i] = Math.random(); Out.print("72 72 translate "); Out.print("/dot {moveto currentpoint"); Out.println(" 2 0 360 arc fill} def"); sort(a, 0, N-1); } } While some details vary, you usually can run the animation by starting an appletviewer or a browser with an .html file containing the following HTML code:
<applet code=SortAnimate.class width=640 height=480> <param name=N value="200"> </applet>
In many Java implementations, this simple strategy provides a very effective animation; in others, the animation may not run smoothly depending on the system load, buffering strategies and other factors.
It is beyond the scope of this book to examine all of the issues involved in developing effective animations; on the other hand, getting a basic animation like this one working is well worth the effort. For example, we can get an effective animation for any exchange-based sorting algorithm in Program 6.17 without changing the sort code at all.
It is important to bear in mind that we should not draw conclusions about performance from visualizations and animations unless we have been careful in building them. For example, if we animate selection sort with Program 6.16, the animation finishes far faster than for insertion sort, simply because, as we have already noted, selection sort does so few exchanges. If we were to instrument comparisons as well as exchanges in the animation, then the relative performance of the animations would be more representative of the relative performance of the algorithms.
Worse, we often find ourselves watching performance properties of a graphics system rather than our algorithms. For example, one way to make the animation in Programs 6.16 and 6.17 operate more smoothly for small examples is to use the repaint() operation periodically. But repaint() can be overly expensive: for example, if we want to animate an algorithm that does millions of exchanges, the approach of repainting on each exchange will collapse because of the time required to do millions (or even thousands) of repaint() operations.
Such pitfalls aside, visual representations can play a critical role in helping us understand how algorithms work, and we shall be using them liberally in figures throughout the book. We could also have exercises for each algorithm asking you to visualize and animate it, because each algorithm, each visual representaion, and each animation can be augmented in all sorts of interesting ways. We refrain from doing so because most readers are likely to be drawn into working with visual representations when they are appropriate, particularly for sorting algorithms. Once you have used a program such as Program 6.15 or Programs 6.16 and 6.17, you are likely to enjoy using programs like them them to visualize other algorithms, and you are certainly encouraged to do so.
Program 6.16 Animating a sorting algorithm
This abstract class provides basic methods in support of animating sorting algorithms (see Program 6.17).
import java.applet.Applet; import java.awt.*; abstract public class Animate extends Applet implements Runnable { Graphics g; Thread animatorThread; int N; double[] a; public void start() { g = getGraphics(); new Thread(this).start(); } public void stop() { animatorThread = null; } public void run() { N = Integer.parseInt(getParameter("N")); a = new double[N]; for (int i = 0; i < N; i++) { a[i] = Math.random(); dot(X(i), Y(a[i]), Color.black); } sort(a, 0, N-1); } int X(int i) { return (i*getSize().width)/N; } int Y(double v) { return (1.0 - v)*getSize().height; } void dot(int x, int y, Color c) { g.setColor(c); g.fillOval(x, y, 5, 5); } void exch(double [] a, int i, int j) { double t = a[i]; a[i] = a[j]; a[j] = t; dot(X(i), Y(a[j]), Color.red); dot(X(j), Y(a[i]), Color.red); dot(X(i), Y(a[i]), Color.black); dot(X(j), Y(a[j]), Color.black); } abstract void sort(double a[], int l, int r); } Program 6.17 Animating a sorting algorithm
This class, which extends Program 6.16, animates the insertion sort in Program 6.6, producing a visual represenation on the screen like the ones in Figures 6.6 and 6.8, but with the dots moving into place. The dots also leave tracks, so the resulting display gives a history of the sort. Since the implementation is based on instrumenting the exch method, it is immediately effective for any exchange-based sort. Similar instrumentation of less is advisable (see Exercise 6.44).
import java.awt.*; public class SortAnimate extends Animate { void sort(double a[], int l, int r) { for (int i = l+1; i <= r; i++) for (int j = i; j > l; j--) if (a[j] < a[j-1]) exch(a, j-1, j); } } Exercises
6.42 Write a version of Program 6.15 that uses appropriate methods from the Java Graphics2D class to draw the visualization on your display.
6.43 Implement insertion, selection, and bubble sort in PostScript, and use your implementation to draw figures like Figures 6.6 through 6.8. You may either try a recursive implementation or read the manual to learn about loops and arrays in PostScript.
| Top |
EAN: 2147483647
Pages: 158