/* Viewing Sources */
/*
Nhan Le
<applet code="SortLabApplet" width="200" height="600"></applet>
*/
import java.applet.Applet;
import java.awt.Graphics;
import java.awt.Canvas;
import java.awt.GridLayout;
import java.awt.Color;
import java.util.Random;
import java.awt.Component;
import java.awt.Image;
public class SortLabApplet extends Applet{
public final int width=200;
public final int height=600;
private Sort[] list = {
new BubbleSort(),
new InsertionSort(),
new SelectionSort(),
new ShellSort(),
//new QuickSort("fix me"),
//new MergeSort("fix me")
};
public void init(){
this.setLayout(new GridLayout(list.length, 1));
for(int i=0; i<list.length; i++){
list[i].setSize(width, height/list.length);
add(list[i]);
}
//after all as been initialized, start sorts
for(int i=0; i<list.length; i++)
list[i].startsort();
}
public String getAppletInfo(){
return "created by Nhan Le <[email protected]>, <[email protected]>";
}
public abstract class Sort extends Canvas{
public void startsort(){}
}
public class SortSkeleton extends Sort{
/*members to be inherited*/
protected String name;
protected long start_time_milli;
protected long sort_time_milli;
protected boolean sortdone = false;
protected int i;
protected int j;
protected int[] array;
protected Thread self;
protected Image ibuffer;//used for double buffering
protected Graphics gbuffer;//used for double buffering
/*internal constants*/
protected final int ARRAY_LENGTH = 100;
protected final int canvas_bottom = 100;//same as canvas height
protected final int canvas_top = 0;
protected final int canvas_width = 200;
protected final int string_height = 10;
protected final int string_xshift = 10;
public void paint(Graphics g){
if(gbuffer == null){
ibuffer = createImage(200,100);
gbuffer = ibuffer.getGraphics();
gbuffer.setColor(Color.black);
gbuffer.fillRect(0,0,200,100);
}
//erase previous by drawing over with black
gbuffer.setColor(Color.black);
for(int v=0; v<array.length; v++)
gbuffer.drawLine(v,canvas_bottom,v,canvas_top);
//draw bars
gbuffer.setColor(Color.blue);
for(int v=0; v<array.length; v++)
gbuffer.drawLine(v,canvas_bottom,v,canvas_bottom-array[v]);
gbuffer.setColor(Color.yellow);
gbuffer.drawLine(i,canvas_bottom,i,canvas_top);
gbuffer.setColor(Color.green);
gbuffer.drawLine(j,canvas_bottom,j,canvas_top);
//draw sort name
gbuffer.setColor(Color.red);
gbuffer.drawString(name,string_xshift,string_height);
if(sortdone){
gbuffer.setColor(Color.white);
gbuffer.drawString("t: "+sort_time_milli+"ms",
canvas_width/2,
(canvas_bottom/2)+(string_height/2)
);
}
g.drawImage(ibuffer, 0,0, this);
}
public void update(Graphics g){
/* just paint on top of current canvas;
no need to waste cpu cycles on repaints of background */
paint(g);
}
protected void shuffle(){//just randomly swap an ordered array
Random r = new Random();
r.setSeed(r.nextLong());
array = new int[ARRAY_LENGTH];
for(int i=0; i<array.length; i++)
array[i] = i;
int a, b, temp;
for(int i=0; i<array.length; i++){
a = Math.abs(r.nextInt()%array.length);
b = Math.abs(r.nextInt()%array.length);
temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
}
public class BubbleSort extends SortSkeleton implements Runnable{
public BubbleSort(){
this("generic");
}
public BubbleSort(String name){
this.name = "Bubble Sort (" + name + ")";
shuffle();
self = new Thread(this);
}
public void startsort(){
start_time_milli = System.currentTimeMillis();
self.start();
}
public void run(){
try{
while(!sortdone){
i=0;
j=0;
int temp;
boolean swapped = false;
for(; i<array.length-1; i++){
for(j=array.length-1; j>i; j--){
if(array[j]<array[j-1]){
swapped = true;
temp = array[j];
array[j] = array[i];
array[i] = temp;
repaint();
Thread.sleep(2);
}
}
}
if(!swapped){
sort_time_milli = System.currentTimeMillis() - start_time_milli;
sortdone = true;
repaint();
}
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public class InsertionSort extends SortSkeleton implements Runnable{
public InsertionSort(){
this("generic");
}
public InsertionSort(String name){
this.name = "Insertion Sort (" + name + ")";
shuffle();
self = new Thread(this);
}
public void startsort(){
start_time_milli = System.currentTimeMillis();
self.start();
}
public void run(){
try{
while(!sortdone){
i=1;
j=0;
int temp;
boolean swapped = false;
for(; i<array.length-1; i++){
for(j=i; (j>0)&&(array[j]<array[j-1]); j--){
swapped = true;
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
repaint();
Thread.sleep(2);
}
}
if(!swapped){
sort_time_milli = System.currentTimeMillis() - start_time_milli;
sortdone = true;
repaint();
}
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public class SelectionSort extends SortSkeleton implements Runnable{
public SelectionSort(){
this("generic");
}
public SelectionSort(String name){
this.name = "Selection Sort (" + name + ")";
shuffle();
self = new Thread(this);
}
public void startsort(){
start_time_milli = System.currentTimeMillis();
self.start();
}
public void run(){
try{
while(!sortdone){
i=0;
j=0;
int lessindex;
int temp;
boolean searching = false;
for(; i<array.length-1; i++){
lessindex = i;
for(j=array.length-1; j>i; j--){
if(array[j]<array[lessindex]){
lessindex = j;
searching=true;
}
temp = array[i];
array[i] = array[lessindex];
array[lessindex] = temp;
repaint();
Thread.sleep(2);
}
}
if(!searching){
sort_time_milli = System.currentTimeMillis() - start_time_milli;
sortdone = true;
repaint();
}
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public class ShellSort extends SortSkeleton implements Runnable{
public ShellSort(){
this("generic");
}
public ShellSort(String name){
this.name = "Shell Sort (" + name + ")";
shuffle();
self = new Thread(this);
}
public void startsort(){
start_time_milli = System.currentTimeMillis();
self.start();
}
public void run(){
try{
while(!sortdone){
int temp;
/**
* A shell sort demonstration algorithm
* SortAlgorithm.java, Thu Oct 27 10:32:32 1994
* Note: Invented by Donald Lewis Shell [CACM, July, 1929, pages 30-32]
* @author Jason [email protected] * @version 1.0, 23 Jun 1992
* @version 1.1, 12 Apr 2000
* -- fixed java.lang.ArrayIndexOutOfBoundsException * Joel Berry found this bug
* -- small modification for adaptation - Nhan Le*/
int h = 1;
/* * find the largest h value possible */
while((h*3 + 1) < array.length)
h = 3*h + 1;
while (h > 0 ) {
/* * for each set of elements (there are h sets) */
for (i=h-1; i < array.length; i++) {
/* * pick the last element in the set */
int B = array[i];
j=i;
/*
* compare the element at B to the one before it in the set
* if they are out of order continue this loop, moving
* elements "back" to make room for B to be inserted. */
for(j=i; (j>=h)&&(array[j-h]>B); j-=h){
array[j] = array[j-h];
Thread.sleep(2);
repaint();
}
/* * insert B into the correct place */
array[j] = B;
}
/* * all sets h-sorted, now decrease set size */
h/=3;
}
sort_time_milli = System.currentTimeMillis() - start_time_milli;
sortdone = true;
repaint();
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public class QuickSort extends SortSkeleton implements Runnable{
public QuickSort(){
this("generic");
}
public QuickSort(String name){
this.name = "Quick Sort (" + name + ")";
shuffle();
self = new Thread(this);
}
public void startsort(){
start_time_milli = System.currentTimeMillis();
self.start();
}
public void run(){
try{
while(!sortdone){
int temp;
/**
* A shell sort demonstration algorithm
* SortAlgorithm.java, Thu Oct 27 10:32:32 1994
* Note: Invented by Donald Lewis Shell [CACM, July, 1929, pages 30-32]
* @author Jason [email protected] * @version 1.0, 23 Jun 1992
* @version 1.1, 12 Apr 2000
* -- fixed java.lang.ArrayIndexOutOfBoundsException * Joel Berry found this bug
* -- small modification for adaptation - Nhan Le*/
int h = 1;
/* * find the largest h value possible */
while((h*3 + 1) < array.length)
h = 3*h + 1;
while (h > 0 ) {
/* * for each set of elements (there are h sets) */
for (i=h-1; i < array.length; i++) {
/* * pick the last element in the set */
int B = array[i];
j=i;
/*
* compare the element at B to the one before it in the set
* if they are out of order continue this loop, moving
* elements "back" to make room for B to be inserted. */
for(j=i; (j>=h)&&(array[j-h]>B); j-=h){
array[j] = array[j-h];
Thread.sleep(2);
}
/* * insert B into the correct place */
array[j] = B;
}
/* * all sets h-sorted, now decrease set size */
h/=3;
}
sort_time_milli = System.currentTimeMillis() - start_time_milli;
sortdone = true;
repaint();
}
}catch(Exception e){
e.printStackTrace();
}
}
}
public class MergeSort extends SortSkeleton implements Runnable{
public MergeSort(){
this("generic");
}
public MergeSort(String name){
this.name = "Merge Sort (" + name + ")";
shuffle();
self = new Thread(this);
}
public void startsort(){
start_time_milli = System.currentTimeMillis();
self.start();
}
public void run(){
try{
while(!sortdone){
int temp;
/**
* A shell sort demonstration algorithm
* SortAlgorithm.java, Thu Oct 27 10:32:32 1994
* Note: Invented by Donald Lewis Shell [CACM, July, 1929, pages 30-32]
* @author Jason [email protected] * @version 1.0, 23 Jun 1992
* @version 1.1, 12 Apr 2000
* -- fixed java.lang.ArrayIndexOutOfBoundsException * Joel Berry found this bug
* -- small modification for adaptation - Nhan Le*/
int h = 1;
/* * find the largest h value possible */
while((h*3 + 1) < array.length)
h = 3*h + 1;
while (h > 0 ) {
/* * for each set of elements (there are h sets) */
for (i=h-1; i < array.length; i++) {
/* * pick the last element in the set */
int B = array[i];
j=i;
/*
* compare the element at B to the one before it in the set
* if they are out of order continue this loop, moving
* elements "back" to make room for B to be inserted. */
for(j=i; (j>=h)&&(array[j-h]>B); j-=h){
array[j] = array[j-h];
Thread.sleep(2);
}
/* * insert B into the correct place */
array[j] = B;
}
/* * all sets h-sorted, now decrease set size */
h/=3;
}
sort_time_milli = System.currentTimeMillis() - start_time_milli;
sortdone = true;
repaint();
}
}catch(Exception e){
e.printStackTrace();
}
}
}
}