//Array sorting algorithms 
//Author: Patrick Campeau
//Version 0.7
//To add:
//-mergeSort
//-quickSort
//-comments for all functions

import java.util.Arrays;

public class Sorting 
{
	public static void main(String[] args)
	{
		int[] data = new int[48000];
		for (int i=0; i<data.length; i++)
		{
			data[i] = (int)(Math.random()*500);
		}
		//insertion sort = 75ms for 10000 elements
		//selection sort = 62ms for 10000 elements
		//bubble sort = 180ms for 10000 elements

		long time1 = System.currentTimeMillis();
		System.out.println(Arrays.toString(data));  
		//selectionSort(data);
		Arrays.sort(data);
		//shuffle(data);
		System.out.println(Arrays.toString(data));
		long time2 = System.currentTimeMillis();
		long elapsedms = (time2 - time1);			//elapsed time in milliseconds
		System.out.println("Elapsed time:" + elapsedms + " ms");
	}
	
	public static void insertionSort(int[] a)
	{
		for (int i=0; i<a.length; i++)
		{
			int j=i;
			while (j>0 && a[j] < a[j-1])
			{
				swap(a, j, j-1);
				j--;
			}
		}
	}
	

	
	public static void bubbleSort(int[] a)
	{
		for (int i=0; i<a.length; i++)
		{
			for (int j=0; j<a.length-i-1; j++)
			{
				if (a[j] > a[j+1])
				{
					swap(a, j, j+1);
				}
			}
		}
	}
	
	public static void selectionSort(int[] a)
	{
		for (int i=0; i<a.length; i++)
		{
			//Find the minimum value's index from i to the end
			int minIndex = i;
			for (int j=i; j<a.length; j++)
			{
				if (a[j] < a[minIndex])
				{
					minIndex = j;
				}
			}
			//Swap minIndex and i (the place for the min value).
			swap(a, i, minIndex);
		}
	}

	//========================================================================
	//BOGOSORT
	//The worst sorting algorithm of all time?  It shuffles the array randomly
	//and checks if it is in order.  If not, it restarts all over again.  Yes,
	//this is a ridiculous strategy! :)
	//
	//Try it for a small enough array!  And consider removing the // to see 
	//how many attempts are needed to sort the array.
	//=========================================================================
	
	public static void bogoSort(int[] a)
	{
		int attempts = 0;
		while (isSorted(a) == false)
		{
			shuffle(a);
			attempts++;
		}
		System.out.println("Attempts:" + attempts);
	}	
	
	//========================================================================
	//BOZOSORT
	//Similar to BogoSort, this algorithm randomly swaps two elements and then
	//checks if the array is in order.  Eventually, after too many swaps, the
	//array is finally in order.  This bad algorithm is actually better than
	//BogoSort!
	//
	//Consider trying this bad algorithm and removing the // to see how many
	//total swaps are needed.
	//========================================================================
	
	public static void bozoSort(int[] a)
	{
		int totalSwaps = 0;
		while (isSorted(a) == false)
		{
			int i = (int)(Math.random() * a.length);
			int j = (int)(Math.random() * a.length);
			swap(a,i,j);
			totalSwaps++;
		}	
		System.out.println("Total swaps required: " + totalSwaps);
	}
	
	
	public static boolean isSorted(int[] a)
	{
		for(int i=0; i<a.length-1; i++)
		{
			if (a[i] > a[i+1])
			{
				return false;
			}
		}
		return true;
	}
	
	public static void shuffle(int[] a)  //Fisher-Yates shuffle algorithm
	{
		for (int i=a.length-1; i>=0; i--)
		{
			int j = (int)(Math.random() * (i+1));  //0 to i
			swap(a, j, i);
		}
	}
	
	public static void naiveShuffle(int[] a)  //bad algorithm because not all possible outcomes have the same odds of occurring
	{
		for (int i=0; i<a.length; i++)
		{
			int j = (int)(Math.random() * a.length);
			swap(a,i,j);
		}
	}
	
	
	public static void swap(int[] a, int index1, int index2)
	{
		int tmp = a[index1];
		a[index1] = a[index2];
		a[index2] = tmp;
	}
}