public class BubbleSort extends Sorter
{	
	public int[] sort(int[] array)
	{
		boolean swapped;
		
		do
		{
			swapped = false;
			for (int i = 0; i < array.length - 1; i++)
			{
				if (this.compare(array[i], array[i+1]))
				{
					this.swap(array, i, i+1);
					swapped = true;
				}
			}
		} while (swapped);
		
		return array;
	}
	
	public static void main(String[] args)
	{
		///// BEST CASE /////
		BubbleSort BS1  = new BubbleSort();
		int[] goodArray = new int[ArrayHelper.arraySize];
		for (int i = 1; i <= goodArray.length; i++)
		{
			goodArray[i-1] = i;
		}
		BS1.sort(goodArray);
		System.out.println("-----------------------------------");
		System.out.println("BubbleSort (best case O(n)):");
		System.out.println("-----------------------------------");
		System.out.println("Number of comparisons: " + BS1.comparisons);
		System.out.println("Number of swaps      : " + BS1.swaps);
		System.out.println("-----------------------------------");
		
		///// WORST CASE /////
		BubbleSort BS2 = new BubbleSort();
		int[] badArray = new int[ArrayHelper.arraySize];
		for (int i = 1; i <= badArray.length; i++)
		{
			badArray[badArray.length - i] = i;
		}
		BS2.sort(badArray);
		System.out.println("-----------------------------------");
		System.out.println("BubbleSort (worst case O(n^2)):");
		System.out.println("-----------------------------------");
		System.out.println("Number of comparisons: " + BS2.comparisons);
		System.out.println("Number of swaps      : " + BS2.swaps);
		System.out.println("-----------------------------------");
		
		///// AVERAGE CASE /////
		int sumOfComparisons = 0;
		int sumOfSwaps       = 0;
		int numberOfRuns     = 10;
		for (int i = 0; i < numberOfRuns; i++)
		{
			BubbleSort BS = new BubbleSort();
			int[] array   = ArrayHelper.initArray();
			BS.sort(array);
			
			sumOfComparisons += BS.comparisons;
			sumOfSwaps       += BS.swaps;
		}
		System.out.println("-----------------------------------");
		System.out.println("BubbleSort (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("-----------------------------------");
	}
}