///////    Quicksort.java    ///////

public class Quicksort implements SortAlgorithm
{
    public void sort(Sortable any)
    {   if (! any.sorted() )
        {   quicksort(any, any.first(), any.last() );
            any.sorted(true);
        }
    }

    public void sort(Sortable any, int l, int r)
    {   if ( ! any.sorted() )
             quicksort(any, l, r);
    }

    protected void quicksort(Sortable any, int l, int r)
    {   if ( l >= r || l < 0 || r < 0 ) return;
        int k = partition(any, l, r);
        quicksort(any, l, k-1);
        quicksort(any, k+1, r);  
    }

    protected int partition(Sortable any, int l, int r)
    {  int i=l, j=r;
       // choose a pivot element
          any.swap(pickPivot(l,r), r);               // pivot moved to r
          while (i < j)
          {  while (any.compare(i, r) <= 0 && i < j) // from left side
                i++; 
             while(j > i && any.compare(j, r) >= 0)  // from right side
                j--;
             if (i < j) any.swap(i++,j);             // switch elements
          }
          if (i != r) any.swap(i,r);                 // pivot element in place
          return(i);
    }

    /** returns index, i <= index  <= j */
    protected int pickPivot(int i, int j)
    {   return (i+j)/2;
    }
}