/******************************************************************************
Quicksort
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.searchAndSort;
import FlexOr.container.*;

/** Sort an array of objects using quicksort.

<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public class Quicksort implements ArraySort {

/**
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public void sort(final Object[] array, final BinaryPredicate bp) {
       execute(array, bp);
   }

/** The quicksort method.

@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
   public static void execute(final Object[] array, final BinaryPredicate bp) {
     quicksort(array, 0, array.length-1, bp);
   }
   
  //Loop invariant: ???
  
   private static void quicksort(final Object[] array,
                          final int lowerIndex, final int upperIndex,
                          final BinaryPredicate bp) {     
       if (lowerIndex >= upperIndex) return;

       Object pivotValue = array[lowerIndex], tmp;
       int splitIndex = lowerIndex;
       
       for (int i = lowerIndex+1 ; i <= upperIndex ; i++) {
           if (bp.execute(array[i], pivotValue)) {
               splitIndex++;
               tmp = array[splitIndex]; array[splitIndex] = array[i];
               array[i] = tmp;
           }
       }

       tmp = array[splitIndex]; array[splitIndex] = pivotValue;
       array[lowerIndex] = tmp;

       if (splitIndex - lowerIndex > upperIndex - splitIndex) {
           quicksort(array, splitIndex+1, upperIndex, bp);
           quicksort(array, lowerIndex, splitIndex-1, bp);
       }
       
      else {
           quicksort(array, lowerIndex, splitIndex-1, bp);
           quicksort(array, splitIndex+1, upperIndex, bp);
      }
   }
}