public class BubbleSorter extends ASorter
{
	public final static BubbleSorter Singleton = new BubbleSorter ();

	private BubbleSorter()
	{
	}

	/**
	 * Splits A[lo:hi] into A[lo:lo] and A[lo+1:hi] in such a way that adjacent
    * elements in A[lo:hi] are compared and swapped if they are out of order,
    * and in the end, the smallest element is "bubbled up" to become A[lo].
 	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 * @return lo+1 ///???? student to fill out what the split index should be.
	 */
	public int split(int[] A, int lo, int hi)
	{
      int j = hi;
      while (lo < j)
      {
         if (A[j] < A[j-1])
         {
            int temp = A[j];
            A[j] = A[j-1];
            A[j-1] = temp;
         }
         j--;
      }
      Utility.printArray(A, 0, A.length-1); // for illustration purpose only.
		return lo + 1;
	}

	/**
	 * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
	 * @param A A[lo:s-1] and A[s:hi] are sorted.
	 * @param lo the low index of A.
	 * @param s the split index.
	 * @param hi the high index of A.
	 */
	public void join(int[] A, int lo, int s, int hi)
	{
	}

   /**
   * Tests BubbleSorter.
   */
	public static void main(String[] args)
	{
      int[] A = {99, -34, 0, 5, -7, 0};
      System.out.print ("\nA = ");
      Utility.printArray(A, 0, A.length-1);
      System.out.println ("\nBubble sorting A...");
      BubbleSorter.Singleton.sort (A, 0, A.length - 1);
      System.out.println ("Sorting done!!!");
      System.out.print ("\nA = ");
      Utility.printArray(A, 0, A.length-1);
	}
}