/*******************************/
/*			       */
/*　　並べ替え（ソーティング） */
/*			       */
/*     1997/11/21 宍戸　輝光   */
/*			       */
/*******************************/

import java.awt.*;
import java.util.Random;

public class sorting extends java.applet.Applet implements Runnable {

	Image sc1,sc2;
	Graphics g_sc1,g_sc2;

	int i,j,k,w,n,cpn,exn;

	int data[]=new int[32];
	int sorted[]=new int[32];
	boolean go;

	Thread runner=null;
	Random rnd=new Random();

	Button go_b,clear16_b,clear32_b;
	Choice sortm;

	Label cpL,exL;

	public void init(){

		resize(340,300);
		setBackground(Color.green);
		setFont(new Font("TimesRoman",Font.PLAIN,12));

		sc1=createImage(194,97); /* データ表示用イメージ */
		g_sc1=sc1.getGraphics();

		sc2=createImage(194,97); /* ソート表示用イメージ */
		g_sc2=sc2.getGraphics();

		this.setLayout((LayoutManager)null);

		go_b=new Button("Start"); /* ソート実行ボタン */
		add(go_b);
		go_b.reshape(8,232,80,28);

		clear16_b=new Button("Clear(n=16)"); /* １６個のデータでクリア */
		add(clear16_b);
		clear16_b.reshape(108,210,128,28);

		clear32_b=new Button("Clear(n=32)"); /* ３２個のデータでクリア */
		add(clear32_b);
		clear32_b.reshape(108,256,128,28);

		sortm=new Choice();
		sortm.addItem("Selection Sort");
		sortm.addItem("Bubble Sort");
		add(sortm);
		sortm.reshape(204,64,128,24);

		cpL=new Label("Compare     "); /* 比較回数表示用のラベル */
		add(cpL);
		cpL.reshape(204,128,96,24);
		cpL.setBackground(Color.green);

		exL=new Label("Exchange     "); /* 交換回数表示用のラベル */
		add(exL);
		exL.reshape(204,160,96,24);
		exL.setBackground(Color.green);

		screenClear(sc1);
		screenClear(sc2);

		n=16; /* 最初に１６個のデータを作り表示する */
		dataMake();

	}

	public void stop() {

		if (runner!=null) {

			runner.stop();
			runner=null;

		}

	}

	public void screenClear(Image sc) { /* イメージをクリア */

		Graphics g_sc=sc.getGraphics();

		g_sc.setColor(Color.white);
		g_sc.fillRect(0,0,193,96);

		g_sc.setColor(Color.black);
		g_sc.drawRect(0,0,193,96);

	}

	public void dataMake() { /* 乱数でデータ作成 */

		for (i=0;i<n;i++) { /* 0-31 の乱数をデータにする */

			data[i]=Math.abs(rnd.nextInt()) % 32;

		}

		drawData(sc1); /* データを表示 */
		drawData(sc2);

		repaint();

	}

	public void drawData(Image sc) { /* データを描画 */

		Graphics g_sc=sc.getGraphics();

		screenClear(sc);

		g_sc.setColor(Color.blue);

		for (i=0;i<n;i++)
			g_sc.fillRect(i*6+2,96-data[i]*3,3,data[i]*3);

	}

	public void SelectionSort() { /* 直接選択ソート本体 */

		cpn=0; /* 比較回数カウンタクリア */
		exn=0; /* 交換回数カウンタクリア */

		for (i=0;i<n-1;i++)
			for (j=i;j<n;j++) {

				if (data[j]<data[i]) {

					w=data[j]; /* 先頭より小さければ交換 */
					data[j]=data[i];
					data[i]=w;

					exn++; /* 交換回数カウンタ+1 */

				}

				cpn++; /* 比較回数カウンタ+1 */

				drawSorted(i,j); /* ソートの様子を描画 */

				if (!go) /* クリアされていたら終了 */
					break;

				try {Thread.sleep(150);} /* 150msウエイト */
				catch (InterruptedException e) {}

			}

	}

	public void BubbleSort() { /* バブルソート本体 */

		cpn=0; /* 比較回数カウンタクリア */
		exn=0; /* 交換回数カウンタクリア */

		for (i=0;i<n-1;i++)
			for (j=0;j<n-i-1;j++) {

				if (data[j]>data[j+1]) {

					w=data[j];
					data[j]=data[j+1];
					data[j+1]=w;

					exn++; /* 交換回数カウンタ+1 */

				}

				cpn++; /* 比較回数カウンタ+1 */

				drawSorted(j,j+1); /* ソートの様子を描画 */

				if (!go) /* クリアされていたら終了 */
					break;

				try {Thread.sleep(150);} /* 150msウエイト */
				catch (InterruptedException e) {}

			}

	}

	public void drawSorted(int a,int b) { /* ソートの様子を描画 */

		screenClear(sc2); /* ソート描画用イメージをクリア */

		for (k=0;k<n;k++) {

			if (k==a || k==b) /* 比較・交換対象なら赤で描く */
				g_sc2.setColor(Color.red);
			else
				g_sc2.setColor(Color.blue);

			g_sc2.fillRect(k*6+2,96-data[k]*3,3,data[k]*3);

		}

		cpL.setText("Compare "+String.valueOf(cpn)); /* 比較回数表示 */
		exL.setText("Exchange "+String.valueOf(exn)); /* 交換回数表示 */

		repaint();

	}

	public void run() {

		while (runner!=null) {

			if (sortm.getSelectedIndex()==0)
				SelectionSort();
			else
				BubbleSort();

			go_b.setLabel("Start");

			runner=null;

		}

	}

	public boolean action(Event evt,Object What) {

		if (evt.target==go_b) { /* Sortボタン */

			if (runner!=null) { /* ソート実行中なら中止 */

				go_b.setLabel("Start");

				go=false; /* スレッド終了 */
				while (runner!=null);

			} else { /* ソート開始 */

				go_b.setLabel("Stop");

				go=true;
				runner=new Thread(this);
				runner.start();

			}

		}

		if (evt.target==clear16_b) { /* １６個のデータでクリア */

			if (runner!=null) {

				go=false;
				while(runner!=null);

			}

			n=16;
			dataMake();

		}

		if (evt.target==clear32_b) { /* ３２個のデータでクリア */

			if (runner!=null) {

				go=false;
				while(runner!=null);

			}

			n=32;
			dataMake();

		}

		return false;

	}

	public void paint(Graphics g){

		g.drawImage(sc1,8,8,this); /*データ表示用イメージを表示*/
		g.drawImage(sc2,8,108,this); /*ソート表示用イメージを表示*/

	}

	public void update(Graphics g){

		paint(g);

	}

}