// 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);

}

}