/**
   A solution to assignment 2.

   Data Structures and Algorithms, CS 305 & 503
   Spring 2010


 */


class ThreeSorting
implements ThreeSorters {

  /**
     Sort an array so that all 1s appear before 2s and all 2s appear before 3s.
     The sort should take O(n) time.

     @param ints An array of zero or more values; each value is either 1, 2, or
     3.  This array should be sorted in place.
   */

  public void 
  linearSolution(int [] ints) {

    final int n = ints.length
    int 
      ones = 0,    // ints[0..ones) == 1
      left = 0,    // ints[ones..left) == 2
      threes = n;  // ints[threes..n) == 3

    while (left < threes)
      if (ints[left] == 1)
	swap(ints, ones++, left++)
      else if (ints[left] == 2)
	left++
      else
	swap(ints, left, --threes)
    }


  /**
     Sort an array so that all 1s appear before 2s and all 2s appear before 3s.
     The sort should take O(n^2) time.

     @param ints An array of zero or more values; each value is either 1, 2, or
     3.  This array should be sorted in place.
   */

  public void 
  nSquareSolution(int [] ints) {

    final int n = ints.length

    for (int i = 0; i < n - 1; i++) {
      int min = i
      for (int j = i + 1; j < n; j++)
	if (ints[min] > ints[j])
	  min = j
      swap(ints, min, i)
      }
    }


  private void
  swap(int ints[], int i, int j) {
    final int t = ints[i]
    ints[i] = ints[j]
    ints[j] = t
    }
  }