import java.io.*;
import java.util.Date;

public class SortingCode
{
	public static void swap(int[] list, int i, int j)
	{
		int temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}
	
	public static void selectionSort(int[] list)
	{
		int index, smallestIndex, minIndex, temp;
		
		for (index = 0; index < list.length-1; index ++)
		{
			//First, find the index of the smallest remaining number in the list.
			smallestIndex = index;
			
			for (minIndex = index + 1; minIndex < list.length; minIndex ++)
				if (list[minIndex] < list[smallestIndex])
					smallestIndex = minIndex;
					
			
			//Now, smallestIndex refers to the position of the smallest number in the list.
			//swap list[index] and list[smallestIndex];
			
			swap(list, index, smallestIndex);
		}
	}
	
	public static void insertionSort(int[] list)
	{
		int index, temp, j;
		
		for (index = 0; index < list.length-1; index ++)
		{
			//We want to decide where in list[0-index] to put list[index+1].
			j = 0;
			temp = index + 1;
			
			while(j <= index && list[j] < list[temp])
				j ++;
			
			//Now j is where list[index + 1] belongs.  We need to push the 
			//elements from j to index up one to make room for list[index+1]
			
			while (temp > j )
			{
				swap(list, temp, temp - 1);
				temp --;
			}
		}
	}
	
	public static void bubbleSort(int[] list)
	{
		int i, j;
		for (i = 0; i < list.length; i ++)
			for (j = i; j < list.length; j ++)
				if (list[i] > list[j]) swap(list, i, j);
				
	}
	
	public static void quicksort(int[] a, int p, int r)
	{
		if (p < r)
		{
			int q = partition(a, p, r);
			quicksort(a, p, q - 1);
			quicksort(a, q + 1, r);
		}
	}
	
	public static int partition(int[] a, int p, int r)
	{
		int x = a[r];
		int i = p - 1;
		
		for (int j = p; j < r; j ++)
		{
			if (a[j] <= x)
			{ 
				i ++;
				swap(a, i, j);
			}
		}
		swap(a, i+1, r);
		return i + 1;
	}
	
	public static void print(int[] list, int end)
	{
		for (int i = 0; i < end; i ++)
		{			
			System.out.print(list[i] + " ");
			
			if (i % 10 == 9) System.out.println();
		}
	}
	
	public static void copyList(int[] from, int[] to)
	{
		for (int i = 0; i < to.length; i ++)
			to[i] = from[i];
	}
	
	
	private static int LISTLENGTH = 100000;
	
	public static void main(String[] args)
	{
		int[] list = new int[LISTLENGTH];
		int[] bklist = new int[LISTLENGTH];
		int i;
		
		for (i = 0; i < LISTLENGTH; i ++)
			bklist[i] = (int) (10*LISTLENGTH*Math.random());

		copyList(bklist, list);
		
		print(list,10);
		
		long t0, t1;
		//print(list);
		
		//System.out.println("\nNow sort the list.");
		t0 = System.currentTimeMillis();
		selectionSort(list);
		t1 = System.currentTimeMillis();				
		System.out.println("Selection sort time: " + (((double)t1 - t0)/1000) + " seconds.");
		
		
		copyList(bklist, list);
		
		t0 = System.currentTimeMillis();
		insertionSort(list);
		t1 = System.currentTimeMillis();
		System.out.println("Insertion sort time: " + (((double)t1 - t0)/1000) + " seconds.");
		
		
		copyList(bklist, list);
		
		t0 = System.currentTimeMillis();
		bubbleSort(list);
		t1 = System.currentTimeMillis();
		System.out.println("Bubble sort time: " + (((double)t1 - t0)/1000) + " seconds.");
		
		
		//print(list, list.length);
		//t0 = System.currentTimeMillis();
		//quicksort(list, 0, list.length-1);
		//t1 = System.currentTimeMillis();
		//System.out.println("Quicksort time: " +  (((double)t1 - t0)/1000) + " seconds.");
		//print(list);
		
		//t0 = System.currentTimeMillis();
		//quicksort(list, 0, list.length-1);
		//t1 = System.currentTimeMillis();
		//System.out.println("Quicksort on sorted list time: " +  (((double)t1 - t0)/1000) + " seconds.");

		//print(bklist);
		//print(list);
		
		//print(list);

	}
}