//#
//# Recursive QuickSort Implementation
//# $Revision: 1.1 $
//# Copyright 2004 by Eric Y. Theriault
//# All Rights Reserved.
//# http://www.eyt.ca/CORBA
//#
package ca.eyt.tests;

/**
 * Demonstrates a Recursive QuickSort Algorithm.  Any book on Data Structures
 * should cover this in more detail, such as WEISS.  This implementation is
 * actually adapted from LADD.
 *
 * Ladd, Scott Robert.  "C++ Components and Algorithms, Second Edition."
 *      M&T Books, 1994.
 * Weiss, Mark Allen.  "Data Structures and Algorithm Analysis in C."
 *      Addison-Wesley-Longman, 1997.
 *
 * @author Eric Y. Theriault <eric@eyt.ca>
 * @version 1.0
 */
public class RecursiveQuickSort extends QuickSort {
   /**
    * Implementation of the QuickSort algorithm, adapted from WEISS.  The
    * original algorithm was defaulting to insertion sort for the last three
    * elements.
    */
   protected void quickSort( Comparable element[], int left, int right ) {
      // Ensure we did not run over.
      if ( left >= right ) {
         return;
      }

      // Pick a random pivot, and initalize the variables.
      Comparable pivot = element[ right ];
      int scanl = left - 1;
      int scanr = right;

      // Loop.
      while ( true ) {
         // Find the first element that is not less than the pivot.
         while ( scanl < scanr ) {
            ++scanl;
            if ( element[ scanl ].compareTo( pivot ) >= 0 ) {
               break;
            }
         }

         // Find the first element that is not greater than the pivot.
         while ( scanr > scanl ) {
            --scanr;
            if ( element[ scanr ].compareTo( pivot ) <= 0 ) {
               break;
            }
         }

         // If these two elements have collided, break.
         if ( scanl >= scanr ) {
            break;
         }

         // Otherwise, swap now.
         swap( element, scanl, scanr );
      }

      // Swap the element with the right most element.
      swap( element, scanl, right );

      // Now use the scanl value as the split point.
      quickSort( element, left, scanl - 1 );
      quickSort( element, scanl + 1, right );
   }

   /**
    * Method to sort an array of elements, based on the Comparable interface.
    * @param element Elements to be sorted.
    */
   public void sort( Comparable element[] ) {
      quickSort( element, 0, element.length - 1 );
   }

   /**
    * Test the algorithm.
    */
   public static void main( String[] args ) {
      test( new RecursiveQuickSort() );
   }
}