/**
 * Sorting2.java
 *
 *
 * Created: Thu Sep 16 15:49:47 1999
 *
 * @author Gareth
 * @version
 */

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

public class Sorting2 extends Applet {

    long time, selectionTime, bubbleTime;
    long revSelectionTime, revBubbleTime, ordSelectionTime, ordBubbleTime;
    long insertionTime, revInsertionTime, ordInsertionTime; 
    int[] array = { 1, 3, 2, 10, 8, 4, 2 };
    TextArea text = new TextArea( 20, 25 );

    public void init(){
	
	}

    public void paint( Graphics g ){

	}

    public Sorting2() {
	this.setLayout( new FlowLayout() );
	this.add( text );
	for( int N = 1000; N<=10000; N+=3000 ){	    
	    int[] x = genArray( N );
	    int[] y = genArray( N );
	    int[] z = genArray( N );
	    int[] r1 = revArray( N );
	    int[] r2 = revArray( N );
	    int[] r3 = revArray( N );
	    int[] o1 = ordArray( N );
	    int[] o2 = ordArray( N );
	    int[] o3 = ordArray( N );
	    time = System.currentTimeMillis();
	    // selection rnd
	    selectionSort( x );
	    selectionTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // bubble rnd
	    bubbleSort( y );
	    bubbleTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // insertion rnd
	    insertionSort( z );
	    insertionTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // selection ord
	    selectionSort( o1 );
	    ordSelectionTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // insertion ord
	    insertionSort( o3 );
	    ordInsertionTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // selection rev
	    selectionSort( r2 );
	    revSelectionTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // insertionrev
	    insertionSort( r3 );
	    revInsertionTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // bubble ord
	    bubbleSort( o2 );
	    ordBubbleTime = System.currentTimeMillis() - time;
	    time = System.currentTimeMillis();
	    // bubble rev
	    bubbleSort( r1 );
	    revBubbleTime = System.currentTimeMillis() - time;
	    text.setText( text.getText() + "\n" + "At N = " + N );
	    text.setText( text.getText() + "\n" + "Selection: " + selectionTime );
	    text.setText( text.getText() + "\n" + "Bubble: " + bubbleTime );
	    text.setText( text.getText() + "\n" + "Insertion: " + insertionTime );
	    text.setText( text.getText() + "\n" + "Selection ordered: " + ordSelectionTime );
	    text.setText( text.getText() + "\n" + "Bubble ordered: " + ordBubbleTime );
	    text.setText( text.getText() + "\n" + "Insertion ordered: " + ordInsertionTime );
	    text.setText( text.getText() + "\n" + "Selection reversed: " + revSelectionTime );
	    text.setText( text.getText() + "\n" + "Bubble reversed: " + revBubbleTime );
	    text.setText( text.getText() + "\n" + "Insertion reversed: " + revInsertionTime );
	    }
	}
    
    //public static void main( String[] args ) {
    //new Sorting();
    //}

    public void bubbleSort( int[] a ){
	for( int j = 0; j < (a.length-1); j++ ){
	    for( int i = 0; i < (a.length-1); i++ ){
		if( a[i] > a[i+1] )
		    swap( a, i, i+1 );
		}
	    }
	}

    public void selectionSort( int[] a ){
	int end = a.length-1;
	while( end > 0 ){
	    int max = findMax( a, end );
	    if( max < end )
		swap( a, max, end );
	    end--;
	    }
	}

    public void insertionSort( int[] a ){
	for( int i=1; i < a.length; i++ ){
	    //System.out.println( "At i = " + i );
	    if( a[i] < a[i-1] ){
		int j = i;
		while( (j>0) && (a[j] <= a[j-1]) ){
		    //System.out.println( "At j = " + j );
		    swap( a, j--, j );
		    }
		}
	    //printArray(a);
	    }
	}

    private int findMax( int[] a, int end ){
	int max = 0;
	for( int i = 0; i < end; i++ )
	    if( a[i] > a[max] )
		max = i;
	return max;
	}
    
    private void swap( int[] a, int index1, int index2 ){
	//System.out.println( "Swapping " + index1 + " & " + index2 );
	int temp = a[index1];
	a[index1] = a[index2];
	a[index2] = temp;
	}

    private void printArray( int[] a  ){
	for( int i = 0; i < (a.length - 1); i++ )
	    System.out.print( a[i] + " " );
	System.out.println( a[a.length-1] );
	}

    private int[] genArray( int n ){
	int[] r = new int[n];
	for( int i = 0; i < n; i++ )
	    r[i] = (int)( ( Math.random() )*12 + 1 );
	return r;
	}

    private int[] ordArray( int n ){
	int[] r = new int[n];
	for( int i = 0; i < n; i++ )
	    r[i] = i;
	return r;
	}

    private int[] revArray( int n ){
	int[] r = new int[n];
	for( int i = n; i > n; i-- )
	    r[i] = i;
	return r;
	}

    } // Sorting