All pastes #249206 Raw Edit

Someone

public text v1 · immutable
#249206 ·published 2006-11-15 15:21 UTC
rendered paste body

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;
   }
}