import java.applet.*;
import java.awt.*;

public class SortingAlgorithms extends Applet implements Runnable
{
	boolean m_fStandAlone = false;

	public static void main(String args[])
	{
		SortingAlgorithmsFrame frame = new SortingAlgorithmsFrame("SortingAlgorithms");

		frame.show();
        frame.hide();
		frame.resize(frame.insets().left + frame.insets().right  + 600,
					 frame.insets().top  + frame.insets().bottom + 400);

		SortingAlgorithms applet_SortingAlgorithms = new SortingAlgorithms();

		frame.add("Center", applet_SortingAlgorithms);
		applet_SortingAlgorithms.m_fStandAlone = true;
		applet_SortingAlgorithms.init();
		applet_SortingAlgorithms.start();
        frame.show();
	}

	public SortingAlgorithms()
	{

	}

	public String getAppletInfo()
	{
		return "Name: SortingAlgorithms\r\n" +
		       "Author: Krishnan Pillaipakkamnatt\r\n" +
		       "";
	}


	public void paint(Graphics g)
	{
		update(g);
	}

	public void init()
	{
		resize(600, 400);
		tempImage = createImage(600,400);
		tg = tempImage.getGraphics();
		dataArray = new int [ NUM_ELEMENTS ];
		rand = new Button ( "Random Data");
		bubble = new Button ( "Bubble" );
		selection = new Button ("Selection");
		insertion = new Button ("Insertion");
		merge = new Button ("Merge");
		quick = new Button ("Quick");
		blockText = new TextField(3);
		add(rand);
		add(bubble);
		add(selection);
		add(insertion);
		add(merge);
		add(quick);
		add(new Label("Block size:"));
		add(blockText);
	}
	
	private int dataArray[];
	private static int blockSize = 2;
	private static int NUM_ELEMENTS	= 600 / blockSize;
	private static int MAX_VALUE		= 400 / blockSize;
	private final static int BUBBLE = 1;
	private final static int SELECTION = 2;
	private final static int MERGE = 3;
	private final static int QUICK = 4;
	private final static int INSERTION = 5;
	private int sortMethod;
	private Button rand, bubble, selection, merge, quick, insertion;
	private TextField blockText;
	private Image tempImage;
	private Graphics tg;


	public void pause (int time) {
		try {
			Thread.sleep(time);
		}catch(Exception e){ }
	}

	public void update (Graphics g){
		int i;

		tg.setColor(Color.black);
		tg.fillRect(0,0,600,400);
		tg.setColor(Color.green);

		for ( i = 0 ; i < NUM_ELEMENTS; i ++ )
			tg.fillRect(blockSize*i,blockSize*dataArray[i],blockSize,blockSize);
		g.drawImage(tempImage,0,0,this);
	}

	private void exchange ( int i, int j ) {
		Graphics g = getGraphics();
		int temp = dataArray[i];
		dataArray[i] = dataArray[j];
		dataArray[j] = temp;

		repaint();
	}

	private void randomData ( ) {
		int i;

		 try {
			blockSize = Integer.parseInt(blockText.getText());
			blockSize = ((blockSize<1)||(blockSize>15))?2:blockSize;
		 } catch (Exception e) { blockSize = 2;}
		 blockText.setText(""+blockSize);

	         NUM_ELEMENTS	= 600 / blockSize;
	         MAX_VALUE		= 400 / blockSize;

		dataArray = new int [ NUM_ELEMENTS ];

		for ( i = 0 ; i < NUM_ELEMENTS ; i++ )
			dataArray[i] = (int)(MAX_VALUE*Math.random());

		repaint();
	}


	private void dispatch ( int sort ) {
		Thread t = new Thread(this);
		t.setPriority(Thread.MIN_PRIORITY);
		sortMethod = sort;
		t.start();
	}

	public boolean action ( Event e, Object o ) {
		if ( e.target == blockText ) {
			randomData();
			return true;
		}
		if ( e.target == rand ) {
			randomData();
			return true;
		}
		if ( e.target == bubble ) {
			dispatch(BUBBLE);
			return true;
		}
		if ( e.target == selection ) {
			dispatch(SELECTION);
			return true;
		}
		if ( e.target == insertion ) {
			dispatch(INSERTION);
			return true;
		}
		if ( e.target == merge ) {
			dispatch(MERGE);
			return true;
		}
		if ( e.target == quick ) {
			dispatch(QUICK);
			return true;
		}

		return false;
	}

	public void run ( ) {
		switch ( sortMethod ) {
		case BUBBLE:
			bubbleSort();
			break;
		case SELECTION:
			selectionSort();
			break;
		case INSERTION:
			insertionSort(0,NUM_ELEMENTS-1);
			break;
		case MERGE:
			mergeSort(0,NUM_ELEMENTS-1);
			break;
		case QUICK:
			quickSort(0,NUM_ELEMENTS-1);
			break;
		default:
			bubbleSort();
		}
	}

	private void insertionSort ( int Astart, int Aend) {
		int i, j, pos;

		for ( i = Astart+1; i <= Aend ; i ++ ){
			pos = i;
			for ( j = i - 1 ; j >= Astart && dataArray[pos] < dataArray[j]; j--){
				exchange(j,pos);
				pos = j;
			}
		}
	}

	private void bubbleSort ( ) {
		int i, j;

		for ( i = 0 ; i < NUM_ELEMENTS - 1 ; i ++ )
			for ( j = 0 ; j < NUM_ELEMENTS - 1 ; j ++ ){
				if ( dataArray[j] > dataArray[j+1] )
					exchange(j, j+1);
		}
	}

	private void selectionSort ( ) {
		int i, j, pos;

		for ( i = 0 ; i < NUM_ELEMENTS - 1 ; i ++ ){
			pos = i;
			for ( j = i+1 ; j < NUM_ELEMENTS ; j ++ )
				if ( dataArray[j] < dataArray[pos] )
					pos = j;

			exchange(i, pos);
			pause(20);
			
		}
	}

	private void quickSort(int i, int j) {
                int pos;
                if ( i >= j )
		    return;
                else if ( (j - i) <= 8 )
                     insertionSort(i,j);
		else {
		    pos = partition(i, j);
                    quickSort(i, pos-1);
                    quickSort(pos+1,j);
                }
        }

	private int partition(int i, int j){
		int pivotPos = i;
                int pivot = dataArray[pivotPos];
		int left, right;

		left = i;
		right = j;
		while ( left <= right ) {
			do {
			    left++;
			} while ( (left < right ) &&
                                (dataArray[left] <= pivot) );

			while ( (right >= left) && (dataArray[right] > pivot)) {
			    right--;
			} 
			if ( left < right )
			    exchange(left, right);
		        pause(5);
		}

		exchange(i, right);
		pause(25);
		return right;
	}

        private int choosePivot(int i, int j){
            int mid = (i+j)/2;

            if ( (dataArray[i] <= dataArray[mid]) &&
                 (dataArray[mid] <= dataArray[j]) ||
                 (dataArray[j] <= dataArray[mid]) &&
                 (dataArray[mid] <= dataArray[i]) )
               return mid;

            if ( (dataArray[i] <= dataArray[j]) &&
                 (dataArray[j] <= dataArray[mid]) ||
                 (dataArray[mid] <= dataArray[j]) &&
                 (dataArray[j] <= dataArray[i]) )
               return j;
        
            return i;
        }

	private void mergeSort(int i, int j) {
		int mid;

		if ( i >= j )
			return;
                else if ( (j-i) <= 8 )
                    insertionSort(i,j);
                else{
		    mid = (i+j)/2;
		    mergeSort(i,mid);
		    mergeSort(mid+1,j);
		    merge(i,mid,j);
                }
	}

	private void merge(int i, int mid, int j){
		int first, second;
		int temp[] = new int[j-i+1];
		int index=0;

		first = i;
		second = mid+1;
		while ( (first <= mid) && (second <= j) ) {
			if ( dataArray[first] < dataArray[second] )
				temp[index++] = dataArray[first++];
			else
				temp[index++] = dataArray[second++];
		}

		if ( first > mid )
			while ( second <= j )
				temp[index++] = dataArray[second++];
		else if ( second > j )
			while ( first <= mid )
				temp[index++] = dataArray[first++];

		index--;
		while ( index >= 0 )
			dataArray[j--] = temp[index--];
		repaint();
		pause(50);
	}
}