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

/**
 * <p>QuickSort common functionality class.  This inheritance is done out of
 * convenience rather than need.</p>
 *
 * Weiss, Mark Allen.  "Data Structures and Algorithm Analysis in C."
 * Addison-Wesley-Longman, 1997.
 *
 * If you have access to the Dr. DOBBS Algorithms and Data Structures CD, this
 * book is one of the many on it.
 *
 * @author Eric Y. Theriault <eric@eyt.ca>
 * @version 1.0
 */
public abstract class QuickSort {
   /**
    * This method is only provided to focus in on the true algorithm.  This
    * simply swaps the element locations within the specified array.
    */
   protected void swap( Comparable element[], int lhs, int rhs ) {
      Comparable temp = element[ lhs ];
      element[ lhs ] = element[ rhs ];
      element[ rhs ] = temp;
   }

   /**
    * Method to sort an array of elements, based on the Comparable interface.
    * @param element Elements to be sorted.
    */
   public abstract void sort( Comparable element[] );

   /**
    * Test Driver Program.  Generates a series of tests to ensure that the
    * elements are properly sorted.
    */
   protected static void test( QuickSort implementation ) {
      final int sizeOfTest = 100;
      Comparable[] element = new Comparable[ sizeOfTest ];

      // Create random data.
      java.util.Random rnd = new java.util.Random();
      System.out.println( "Random Numbers:" );
      for ( int i = 0; i < sizeOfTest; ++i ) {
         element[ i ] = new Integer( rnd.nextInt( Integer.MAX_VALUE ) );
         System.out.println( element[ i ] );
      }

      // Sort
      implementation.sort( element );

      // Display results
      System.out.println();
      System.out.println( "Sorted:" );
      for ( int i = 0; i < sizeOfTest; ++i ) {
         if ( i != 0 && element[ i ].compareTo( element[ i - 1 ] ) < 0 ) {
            System.out.print( "*** " );
         }
         System.out.println( element[ i ] );
      }
   }
}