import java.util.Comparator;

public class QuickSort
implements Sort
{
private Comparator comp = null;

public QuickSort( Comparator c )
{ comp = c; }

public QuickSort()
{}

public void sort( Object [] d )
{ sort( d, 0, d.length - 1 ); }

public void sort( Object [] d, int start, int end )
{
if ( start >= end )
return;

int p = partition( d, start, end );

sort( d, start, p - 1 );
sort( d, p + 1, end );
}

private int partition( Object [] d, int start, int end )
{
Object pivot = d[ end ];
int low = start - 1;
int high = end;

while ( true )
{
while ( compare( d[ ++low ], pivot ) < 0 ) ;
while ( compare( pivot, d[ --high ] ) < 0 && high > low) ;
if ( low >= high ) break;
exchange( d, low, high );
}
exchange( d, low, end );
return low;
}

private void exchange( Object [] a, int i, int j )
{
// inercambia los elementos low y high del array a
Object o = a[ i ];
a[ i ] = a[ j ];
a[ j ] = o;
}

private int compare( Object a, Object b )
{
if ( comp == null )
{
return ((Comparable)a).compareTo( b );
}
else
{
return comp.compare( a, b );
}
}
}