public class InsertionSort extends Sorter
{
	public int[] sort(int[] array)
	{
		for (int i = 1; i < array.length; i++)
		{
			int m = array[i];
			int j = i;
			
			while (j > 0)
			{
				if (this.compare(array[j-1], m))
				{
					this.swap(array, j, j-1);
					j = j - 1;
				}
				else
				{
					break;
				}
			}
		}
		
		return array;
	}

	public static void main(String[] args)
	{
		///// BEST CASE /////
		InsertionSort IS1 = new InsertionSort();
		int[] goodArray   = new int[ArrayHelper.arraySize];
		for (int i = 1; i <= goodArray.length; i++)
		{
			goodArray[i-1] = i;
		}
		IS1.sort(goodArray);	
		System.out.println("-------------------------------------");
		System.out.println("InsertionSort (best case O(n)):");
		System.out.println("-------------------------------------");
		System.out.println("Number of comparisons: " + IS1.comparisons);
		System.out.println("Number of swaps      : " + IS1.swaps);
		System.out.println("-------------------------------------");
		
		///// WORST CASE /////
		InsertionSort IS2 = new InsertionSort();
		int[] badArray = new int[ArrayHelper.arraySize];
		for (int i = 1; i <= badArray.length; i++)
		{
			badArray[badArray.length - i] = i;
		}
		IS2.sort(badArray);
		System.out.println("-------------------------------------");
		System.out.println("InsertionSort (worst case O(n^2)):");
		System.out.println("-------------------------------------");
		System.out.println("Number of comparisons: " + IS2.comparisons);
		System.out.println("Number of swaps      : " + IS2.swaps);
		System.out.println("-------------------------------------");
		
		///// AVERAGE CASE /////
		int sumOfComparisons = 0;
		int sumOfSwaps       = 0;
		int numberOfRuns     = 10;
		for (int i = 0; i < numberOfRuns; i++)
		{
			InsertionSort IS = new InsertionSort();
			int[] array      = ArrayHelper.initArray();
			IS.sort(array);
			
			sumOfComparisons += IS.comparisons;
			sumOfSwaps       += IS.swaps;
		}
		System.out.println("-------------------------------------");
		System.out.println("InsertionSort (average case O(n^2)):");
		System.out.println("-------------------------------------");
		System.out.println("Total number of comparisons: " + sumOfComparisons);
		System.out.println("Total number of swaps      : " + sumOfSwaps);
		System.out.println("-------------------------------------");
		System.out.println("Average number of comparisons: " + sumOfComparisons/numberOfRuns);
		System.out.println("Average number of swaps      : " + sumOfSwaps/numberOfRuns);
		System.out.println("-------------------------------------");
	}
}