Clarification for quicksort

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • Frank Pegot

    #1

    Clarification for quicksort

    I am working out of a Java book and I have a question of what it is asking me to do.

    The question is: Redo the QuickSort class so that it chooses the splitting point as follows: The splitting point is the middle (in size) of the first element, the last element, and the element at approximately the middle of the array. This will make a very uneven split less likely.

    I'm guessing it wants me to choose the average of all the data points, but not sure.

    Here is the code in question
    Code:
    /**
     Class that realizes the divide-and-conquer sorting pattern and
     uses the quick sort algorithm.
    */
    public class QuickSort
    {
    
        /**
         Precondition: Interval a[begin] through a[end] of a have elements.
         Postcondition: The values in the interval have
         been rearranged so that a[begin] <= a[begin+1] <= ... <= a[end].
        */
        public static void sort(double[] a, int begin, int end)
        {
            if ((end - begin) >= 1)
            {
                int splitPoint = split(a, begin, end);
                sort(a, begin, splitPoint);
                sort(a, splitPoint + 1, end);
                join(a, begin, splitPoint, end);
            }//else sorting one (or fewer) elements so do nothing.
        }
    
        private static int split(double[] a, int begin, int end)
        {
            double[] temp;
            int size = (end - begin + 1);
            temp = new double[size];
    
            double splitValue = a[begin];
            int up = 0;
            int down = size - 1;
    
            //Note that a[begin] = splitValue is skipped.
            for (int i = begin + 1; i <= end; i++)
            {
                if (a[i] <= splitValue)
                {
                    temp[up] = a[i];
                    up++;
                }
                else
                {
                    temp[down] = a[i];
                    down--;
                }
            }
    
            //0 <= up = down < size
    
            temp[up] = a[begin]; //Positions the split value, spliV.
    
            //temp[i] <= splitValue for i < up
             // temp[up] = splitValue
             // temp[i] > splitValue for i > up
    
            for (int i = 0; i < size; i++)
                a[begin + i] = temp[i];
    
            return (begin + up);
        }
    
        private static void join(double[] a, int begin,
                                                 int splitPoint, int end)
        {
            //Nothing to do.
        }
    
    }
    Thanks guys
Working...