public class SortingAndSearching<T extends Comparable>
{
/********************************************************************
Sorts the specified array of objects using the quick sort
algorithm.
********************************************************************/
public void quickSort (T[] data, int min, int max)
{
int indexofpartition;
int count = 0;
if (max - min > 0)
{
/** Create partitions */
indexofpartition = findPartition(data, min, max);
/** Sort the left side */
quickSort(data, min, indexofpartition - 1);
/** Sort the right side */
quickSort(data, indexofpartition + 1, max);
}
}
/********************************************************************
Used by the quick sort algorithm to find the partition.
********************************************************************/
private int findPartition (T[] data, int min, int max)
{
int left, right;
T temp, partitionelement;
partitionelement = data[min]; // use first element as partition
left = min;
right = max;
while (left<right)
{
/** search for an element that is > the partitionelement */
while (data[left].compareTo(partitionelement) <=0 &&
left < right)
left++;
/** search for an element that is < the partitionelement */
while (data[right].compareTo(partitionelement) > 0)
right--;
/** swap the elements */
if (left<right)
{
temp = data[left];
data[left] = data[right];
data[right] = temp;
}
}
/** move partition element to partition index*/
temp = data[min];
data[min] = data[right];
data[right] = temp;
return right;
}
}