import tio.*;
import java.util.*;
import binarytree.*;
import binarysearchtree.*;

class Sorting {
    public static void main(String[] args) {
	int arraysize = Integer.parseInt(args[0]);
	int[] theArray = new int[arraysize];
	int[] array2;
	long t1,t2;

	// Initialize the array with random numbers
	initialize(theArray);

	// selection sort
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	selectionsort(array2);
	t2 = new Date().getTime();

	System.out.println("Selection sort took: " + (t2-t1) + " milliseconds");
	dump(array2);

	// bubble sort
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	bubblesort(array2);
	t2 = new Date().getTime();

	System.out.println("Bubble sort took: " + (t2-t1) + " milliseconds");
	dump(array2);

	// bubble sort with a linked list
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	bubblesort2(array2);
	t2 = new Date().getTime();

	System.out.println("Bubble sort2 took: " + (t2-t1) + " milliseconds");
	dump(array2);

	// insertion sort
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	insertionsort(array2);
	t2 = new Date().getTime();

	System.out.println("Insertion sort took: " + (t2-t1) + " milliseconds");
	dump(array2);

	// mergesort
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	mergesort(array2);
	t2 = new Date().getTime();

	System.out.println("Mergesort took: " + (t2-t1) + " milliseconds");
	dump(array2);

	// quicksort
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	quicksort(array2, 0, theArray.length-1);
	t2 = new Date().getTime();

	System.out.println("Quicksort took: " + (t2-t1) + " milliseconds");
	dump(array2);

	// binary search tree sort
	array2 = (int[])theArray.clone();

        t1 = new Date().getTime();
	bstsort(array2);
	t2 = new Date().getTime();

	System.out.println("Binary Search Tree Sort took: " + (t2-t1) + " milliseconds");
	dump(array2);
	
    }

    // Initialize the array
    public static void initialize(int[] theArray) {
	for(int i = 0; i < theArray.length; i++) {
	    theArray[i] = (int)(Math.random()*theArray.length);
	}
    }
    
    // Print out the array
    public static void dump(int[] theArray) {
	if(theArray.length <= 10) {
	    System.out.print("The array: ");
	    for(int i = 0; i < theArray.length; i++)
		System.out.print(theArray[i] + " ");
	}
	System.out.println();
    }


    public static void selectionsort(int[] theArray) {
	int min, temp;

	for(int i = 0; i < theArray.length; i++) {
	    min = i;
	    for(int j = i; j < theArray.length; j++) {
		if(theArray[j] < theArray[min])
		    min = j;
	    }
	    temp = theArray[i];
	    theArray[i] = theArray[min];
	    theArray[min] = temp;
	}
    }

    public static void bubblesort(int[] theArray) {
	int temp;
	boolean done = false;

	while(!done) {
	    done = true;
	    for(int j = 1; j < theArray.length; j++) {
		if (theArray[j] < theArray[j-1]) {
		    temp = theArray[j];
		    theArray[j] = theArray[j-1];
		    theArray[j-1] = temp;
		    done = false;
		}
	    }
	}
    }


    public static void bubblesort2(int[] theArray) {
	int temp;
	boolean done = false;
	DoublyLinkedList d = new DoublyLinkedList();
	Integer i1 = new Integer(0), i2 = new Integer(0);

	// Copy the array into the list
	for(int i = 0; i < theArray.length; i++) {
	    d.add(new Integer(theArray[i]));
	}

	while(!done) {
	    done = true;
	    for(int j = 0; j < theArray.length-1; j++) {
		try {
		    i1 = (Integer)d.get(j);
		} catch(IndexOutOfBoundsException e) {
		    System.out.println(e);
		    System.exit(0);
		}
		try {
		    i2 = (Integer)d.get(j+1);
		} catch(IndexOutOfBoundsException e) {
		    System.out.println(e);
		    System.exit(0);
		}
		if (i1.intValue() > i2.intValue()) {
		    d.swap(j, j+1);
		    done = false;
		}
	    }
	}

	for(int i = 0; i < theArray.length; i++) {
	    i1 = (Integer)d.get(i);
	    theArray[i] = i1.intValue();
	}
    }

    public static void insertionsort(int[] theArray) {
	int i, j, k, num;

	for(i = 0; i < theArray.length; i++) {
	    num = theArray[i];

	    for(j = 0; j < i ; j++) {
		if(theArray[j] > num)
		    break;
	    }

	    for(k = i; k > j; k--) {
		theArray[k] = theArray[k-1];
	    }

	    theArray[j] = num;
	}
    }

    public static void mergesort(int[] theArray) {

	int half = theArray.length/2;
	int[] arr2, arr3;
	int k1=0, k2=0, j;

	if (theArray.length == 1) {   
	    return; 
	} 

	arr2 = new int[half];
	arr3 = new int[theArray.length - arr2.length];

	// Populate the two subarrays
	for(int i = 0; i < theArray.length; i++) {
	    if(i < arr2.length) {
		arr2[i] = theArray[i];
	    } else {
		arr3[i - arr2.length] = theArray[i];
	    }
	}

	// Sort the two halves
	mergesort(arr2);
	mergesort(arr3);

	// Merge the two halves
	for (j=0; 
	     (j < theArray.length)
		 && (k1 < arr2.length) 
		 && (k2 < arr3.length); 
	     j++) {
	    if (arr2[k1] < arr3[k2]) {
		theArray[j] = arr2[k1++]; 
	    } else { 
		theArray[j] = arr3[k2++];
	    }
	}

	while(k1 < arr2.length) {
	    theArray[j++] = arr2[k1++];
	}

	while(k2 < arr3.length) {
	    theArray[j++] = arr3[k2++];
	}

    }

    public static void quicksort(int[] theArray, int start, int end) {
	int pivotElem, tmp;
	int endS1 = start;

	if ((end-start) <= 0)
	    return;

	pivotElem = theArray[start];

	for(int i = start+1; i <= end; i++) {
	    if (theArray[i] <= pivotElem) {
		endS1++;
		tmp = theArray[endS1];
		theArray[endS1] = theArray[i];
		theArray[i] = tmp;
	    }
	}
	theArray[start] = theArray[endS1];
	theArray[endS1] = pivotElem; 

	// Sort the two parts of the array
	quicksort (theArray, start, endS1-1);
	quicksort (theArray, endS1+1, end);
    }

    public static void bstsort(int[] theArray) {
	BinarySearchTree tree = new BinarySearchTree();
	int i;

	for(i = 0; i < theArray.length; i++)
	    tree.insert(new TreeItem(theArray[i]));

	TreeIterator btIterator = new TreeIterator(tree);
	btIterator.setInorder();

	System.out.println("The whole tree, in order:");
	i = 0;
	while(btIterator.hasNext()) {
	    TreeItem t = (TreeItem)btIterator.next();
	    theArray[i] = t.value();
	    i++;
	}
    }
}

class TreeItem extends KeyedItem {
    private int value;

    public TreeItem(int value) {
	super(new Integer(value));
	this.value = value;
    }

    public int value() {
	return value;
    }

    public String toString() {
	return getKey().toString();
    }
}