content: // Copyright (C) 1999 Lucent Technologies
  // From 'Programming Pearls' by Jon Bentley
  
  // SortAnim.java -- Animate sorting algorithms
  
  import java.applet.*;
  import java.awt.*;
  import java.util.Date;
  
  public class SortAnim extends Applet {
  	// Screen Elements
  	private TextField n_text;
  	private Choice dist_choices;
  	private Choice alg_choices;
  	private Button run_button;
  	private Label msg_label;
  	private Color draw_color = Color.black;
  	private Color back_color = Color.white;
  
  // SORTING DATA AND ALGS
  
  	static private final int MAXN = 10000;
  	static private int n=100;
  	static private float a[] = new float[MAXN];
  
  	// Sorting: Generate Inputs
  	static private final int GEN_RAND = 0;
  	static private final int GEN_ASCEND = 1;
  	static private final int GEN_DESCEND = 2;
  	static private int gen_num = GEN_RAND;
  
  	private void genarray()
  	{	for (int i = 0; i < n; i++) {
  			switch(gen_num) {
  			case GEN_RAND: a[i] = (float) Math.random(); break;
  			case GEN_ASCEND: a[i] = ((float) i)/n; break;
  			case GEN_DESCEND: a[i] = (float) (1.0 - ((float) i)/n); break;
  			}
  		}
  	}
  
  	// Sorting: Supporting Algs
  	private void baseswap(int i, int j)
  	{	float t = a[i];
  		a[i] = a[j];
  		a[j] = t;
  	}
  
  	// Sorting: Animation Support
  	static private final int MINX = 20, MAXX = 580;
  	static private final int MINY = 50, MAXY = 380;
  	static private float factorx, factory;
  	static private boolean wantanim = true;
  
  	private void initdisplay()
  	{	Graphics g = this.getGraphics();
  		Rectangle r = this.bounds();
  		g.setColor(back_color);
  		g.fillRect(r.x, r.y, r.width, r.height);
  		factorx = ((float) MAXX-MINX) / n;
  		factory = ((float) MAXY-MINY);
  	}
  
  	private void draw(int i, Color c)
  	{	Graphics g = this.getGraphics();  // BETTER WAY?
  		int d = 4;
  		int px = (int) (MINX + factorx*i);
  		int py = MAXY - (int)(factory*a[i]);
  		g.setColor(c);
  		g.drawOval(px, py, d, d);
  	}
  
  	private void swap(int i, int j)
  	{	if (wantanim) {
  			draw(i, back_color);
  			draw(j, back_color);
  		}
  		baseswap(i, j);
  		if (wantanim) {
  			draw(i, draw_color);
  			draw(j, draw_color);
  		}
  	}
  
  	// Sorting Algs
  	private void isort()
  	{	for (int i = 1; i < n; i++)
  			for (int j = i; j > 0 && a[j-1] > a[j]; j--)
  				swap(j-1, j);
  	}	
  
  	private void ssort()
  	{	for (int i = 0; i < n-1; i++)
  			for (int j = i; j < n; j++)
  				if (a[j] < a[i])
  					swap(i, j);
  	}
  
  	private void shellsort()
  	{	int i, j, h;
  		for (h = 1; h < n; h = 3*h + 1)
  			;
  		for (;;) {
  			h /= 3;
  			if (h < 1) break;
  			for (i = h; i < n; i++) {
  				for (j = i; j >= h; j -= h) {
  					if (a[j-h] < a[j]) break;
  					swap(j-h, j);
  				}
  			}
  		}
  	}
  
  	private void siftdown(int l, int u)
  	{	int i, c;
  		i = l;
  		for (;;) {
  			c = 2*i;
  			if (c > u)
  				break;
  			if (c+1 <= u && a[c+1] > a[c])
  				c++;
  			if (a[i] >= a[c])
  				break;
  			swap(i, c);
  			i = c;
  		}
  	}
  
  	private void heapsort() // BEWARE!!! Sorts x[1..n-1]
  	{	int i;
  		for (i = n/2; i > 0; i--)
  			siftdown(i, n-1);
  		for (i = n-1; i >= 2; i--) {
  			swap(1, i);
  			siftdown(1, i-1);
  		}
  	}
  
  	private void qsort(int l, int u)
  	{	if (l >= u)
  			return;
  		int m = l;
  		for (int i = l+1; i <= u; i++)
  			if (a[i] < a[l])
  				swap(++m, i);
  		swap(l, m);
  		qsort(l, m-1);
  		qsort(m+1, u);
  	}
  
  	void qsort2(int l, int u)
  	{	if (l >= u)
  			return;
  		int i = l;
  		int j = u+1;
  		for (;;) {
  			do i++; while (i <= u && a[i] < a[l]);
  			do j--; while (a[j] > a[l]);
  			if (i > j)
  				break;
  			swap(i, j);
  		}
  		swap(l, j);
  		qsort2(l, j-1);
  		qsort2(j+1, u);
  	}
  
  	// Drive Sort
  	static private final int ALG_ISORT = 0;
  	static private final int ALG_SELSORT = 1;
  	static private final int ALG_SHELLSORT = 2;
  	static private final int ALG_HSORT = 3;
  	static private final int ALG_QSORT = 4;
  	static private final int ALG_QSORT2 = 5;
  	static private int alg_num = ALG_ISORT;
  
  	private void dosort()
  	{	switch(alg_num) {
  		case ALG_ISORT:     isort(); break;
  		case ALG_SELSORT:   ssort(); break;
  		case ALG_SHELLSORT: shellsort(); break;
  		case ALG_HSORT:     heapsort(); break;
  		case ALG_QSORT:     qsort(0, n-1); break;
  		case ALG_QSORT2:    qsort2(0, n-1); break;
  		}
  	}
  
  	private void runanim()
  	{	n = Integer.parseInt(n_text.getText());
  		if (n < 1 || n > MAXN) {
  			n = 50;
  			n_text.setText("" + n);
  		}
  		initdisplay();
  		msg_label.setText("Running");
  		genarray();
  		for (int i = 0; i < n; i++)
  			draw(i, draw_color);
  		Date timer = new Date();
  		long start = timer.getTime();
  		dosort();
  		timer = new Date();
  		long msecs = timer.getTime() - start;
  		msg_label.setText("Msecs: " + msecs);
  		if (! wantanim) // Draw results over input
  			for (int i = 0; i < n; i++)
  				draw(i, draw_color);
  	}
  
  // GUI FUNCTIONS
  	public void init() {
  		this.setBackground(back_color);
  
  		// TextField for n (problem size)
  		n_text = new TextField(5);
  		this.add(new Label("n:"));
  		this.add(n_text);
  		n_text.setText("" + n);
  
  		// Choice of Starting distributions
  		dist_choices = new Choice();
  		dist_choices.addItem("Random");
  		dist_choices.addItem("Ascending");
  		dist_choices.addItem("Descending");
  		this.add(new Label("Input:"));
  		this.add(dist_choices);
  
  		// Choice of Sort Algorithms
  		alg_choices = new Choice();
  		alg_choices.addItem("Insertion Sort");
  		alg_choices.addItem("Selection Sort");
  		alg_choices.addItem("Shell Sort");
  		alg_choices.addItem("Heap Sort");
  		alg_choices.addItem("Quicksort");
  		alg_choices.addItem("2-way Quicksort");
  		this.add(new Label("Algorithm:"));
  		this.add(alg_choices);
  
  		// Run Button
  		run_button = new Button("Run");
  		this.add(run_button);
  
  		// Message Label
  		msg_label = new Label("                   ");
  		this.add(msg_label);
  	}
  
  	public boolean action(Event event, Object arg) {
  		if (event.target == dist_choices) {
  			if (arg.equals("Random")) gen_num = GEN_RAND;
  			else if (arg.equals("Ascending")) gen_num = GEN_ASCEND;
  			else if (arg.equals("Descending")) gen_num = GEN_DESCEND;
  			return true;
  		} else if (event.target == alg_choices) {
  			if (arg.equals("Insertion Sort")) alg_num = ALG_ISORT;
  			else if (arg.equals("Selection Sort")) alg_num = ALG_SELSORT;
  			else if (arg.equals("Shell Sort")) alg_num = ALG_SHELLSORT;
  			else if (arg.equals("Heap Sort")) alg_num = ALG_HSORT;
  			else if (arg.equals("Quicksort")) alg_num = ALG_QSORT;
  			else if (arg.equals("2-way Quicksort")) alg_num = ALG_QSORT2;
  			return true;
  		} else if (event.target == run_button) {
  			runanim();
  			return true;
  		} else
  			return super.action(event, arg);
  	}
  }