Page History

/**
 * A concrete sorter that uses the QuickSort method.
 */
public class QuickSorter extends ASorter
{

 /**
  * The constructor for this class.
  * @param iCompareOp The comparison strategy to use in the sorting.
  */
 public QuickSorter(AOrder iCompareOp)
 {
  super(iCompareOp);
 }
 /**
  * Splits A[lo:hi] into A[lo:s-1] and A[s:hi] where s is the returned value of this function.
  * This method places all values greater than the key at A[0] at indices above the split index 
  * and all values below the key at indices less than the split index.
  * @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 The split index.
  */
 protected int split(Object[] A, int lo, int hi)
 {
      Object key = A[lo];
      int lx = lo; // left index.
      int rx = hi; // right index.
      // Invariant 1: key <= A[rx+1:hi].
      // Invariant 2: A[lo:lx-1] <= key.
      // Invariant 3: there exists ix in [lo:rx] such that A[ix] <= key.
      // Invariant 4: there exists jx in [lx:hi] such that key <= A[jx].
      while (lx <= rx)
      {
         while (aOrder.lt(key, A[rx])) // will terminate due to invariant 3.
         {
            rx--;  // Invariant 1 is maintained.
         } // A[rx] <= key <= A[rx+1:hi]; also  invariant 0, lx <= rx.

         while (aOrder.lt(A[lx], key)) // will terminate due to invariant 4.
         {
            lx++;  // Invariant 2 is maintained.
         } // A[lo:lx-1] <= key <= A[lx]

         if (lx <= rx)
         {
            // swap A[lx] with A[rx]:
            Object temp = A[lx];
            A[lx] = A[rx]; // invariant 3 is maintained.
            A[rx] = temp;  // invariant 4 is maintained.
            rx--;  // invariant 1 is maintained.
            lx++;  // invariant 2 is maintained.
         }
      } // rx < lx, A[lo:lx-1] <= key <= A[rx+1:hi], and key = A[lx].
  return lx;

 }

 /**
  * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
  * This method does nothing, as the sub-arrays are already in proper order.
  * @param A A[lo:s-1] and A[s:hi] are sorted.
  * @param lo the low index of A.
  * @param s 
  * @param hi the high index of A.
  */
 protected void join(Object[] A, int lo, int s, int hi)
 {
 }
}