/** Sort the entire vector, if it is not empty
 */
  public void quickSort(Vector elements)
  { if (! elements.isEmpty())
    { this.quickSort(elements, 0, elements.size()-1);
    }
  }


/**
 * QuickSort.java by Henk Jan Nootenboom, 9 Sep 2002
 * Copyright 2002-2005 SUMit. All Rights Reserved.
 *
 * Algorithm designed by prof C. A. R. Hoare, 1962
 * See http://www.sum-it.nl/en200236.html
 * for algorithm improvement by Henk Jan Nootenboom, 2002.
 *
 * Recursive Quicksort, sorts (part of) a Vector by
 *  1.  Choose a pivot, an element used for comparison
 *  2.  dividing into two parts:
 *      - less than-equal pivot
 *      - and greater than-equal to pivot.
 *      A element that is equal to the pivot may end up in any part.
 *      See www.sum-it.nl/en200236.html for the theory behind this.
 *  3. Sort the parts recursively until there is only one element left.
 *
 * www.sum-it.nl/QuickSort.java this source code
 * www.sum-it.nl/quicksort.php3 demo of this quicksort in a java applet
 *
 * Permission to use, copy, modify, and distribute this java source code
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted.
 * See http://www.sum-it.nl/security/index.html for copyright laws.
 */
  private void quickSort(Vector elements, int lowIndex, int highIndex)
  { int lowToHighIndex;
    int highToLowIndex;
    int pivotIndex;
    String pivotValue;  // values are Strings in this demo, change to suit your application
    String lowToHighValue;
    String highToLowValue;
    String parking;
    int newLowIndex;
    int newHighIndex;
    int compareResult;

    lowToHighIndex = lowIndex;
    highToLowIndex = highIndex;
    /** Choose a pivot, remember it's value
     *  No special action for the pivot element itself.
     *  It will be treated just like any other element.
     */
    pivotIndex = (lowToHighIndex + highToLowIndex) / 2;
    pivotValue = (String)elements.elementAt(pivotIndex);

    /** Split the Vector in two parts.
     *
     *  The lower part will be lowIndex - newHighIndex,
     *  containing elements <= pivot Value
     *
     *  The higher part will be newLowIndex - highIndex,
     *  containting elements >= pivot Value
     */
    newLowIndex = highIndex + 1;
    newHighIndex = lowIndex - 1;
    // loop until low meets high
    while ((newHighIndex + 1) < newLowIndex) // loop until partition complete
    { // loop from low to high to find a candidate for swapping
      lowToHighValue = (String)elements.elementAt(lowToHighIndex);
      while (lowToHighIndex < newLowIndex
        & lowToHighValue.compareTo(pivotValue)<0 )
      { newHighIndex = lowToHighIndex; // add element to lower part
        lowToHighIndex ++;
        lowToHighValue = (String)elements.elementAt(lowToHighIndex);
      }

      // loop from high to low find other candidate for swapping
      highToLowValue = (String)elements.elementAt(highToLowIndex);
      while (newHighIndex <= highToLowIndex
        & (highToLowValue.compareTo(pivotValue)>0)
        )
      { newLowIndex = highToLowIndex; // add element to higher part
        highToLowIndex --;
        highToLowValue = (String)elements.elementAt(highToLowIndex);
      }

      // swap if needed
      if (lowToHighIndex == highToLowIndex) // one last element, may go in either part
      { newHighIndex = lowToHighIndex; // move element arbitrary to lower part
      }
      else if (lowToHighIndex < highToLowIndex) // not last element yet
      { compareResult = lowToHighValue.compareTo(highToLowValue);
        if (compareResult >= 0) // low >= high, swap, even if equal
        { parking = lowToHighValue;
          elements.setElementAt(highToLowValue, lowToHighIndex);
          elements.setElementAt(parking, highToLowIndex);

          newLowIndex = highToLowIndex;
          newHighIndex = lowToHighIndex;

          lowToHighIndex ++;
          highToLowIndex --;
        }
      }
    }

    // Continue recursion for parts that have more than one element
    if (lowIndex < newHighIndex)
    { this.quickSort(elements, lowIndex, newHighIndex); // sort lower subpart
    }
    if (newLowIndex < highIndex)
    { this.quickSort(elements, newLowIndex, highIndex); // sort higher subpart
    }
  }

/**
 * SUMit MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUMit SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUMit
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */