Clarification for quicksort

[Will Huang]

I'm working out of a Java book and I have a question on 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 have no idea how it wants me to define the splitting point. How can the split point be the first element, the last element and the middle element all at the same time?

here is the code in question:

 
/**
 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

[fred rosenberger]

read the directions more carefully:

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.

it doesn't say the split point IS all three. What I think he's trying to say is take the average of the first and last (hence the 'middle of the first and last element'). since that will (more that likely) not be an actual element, choose one in the middle of the array (i.e. if you have 100 elements to sort, pick one around element 50) that would be close to that average.

[Campbell Ritchie]

And welcome to the Ranch

[Will Huang]

fred rosenberger wrote:read the directions more carefully:

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.

it doesn't say the split point IS all three. What I think he's trying to say is take the average of the first and last (hence the 'middle of the first and last element'). since that will (more that likely) not be an actual element, choose one in the middle of the array (i.e. if you have 100 elements to sort, pick one around element 50) that would be close to that average.

Thanks for the help, but which is it? The average of the first and last or the element in the middle of the array?

[Paul Clapham]

You're asking about the meaning of an English sentence. And a very poorly-written one at that. This isn't a Java question, it's a question which should be addressed to the person who wrote the sentence.

I think the "middle in size" part means the median of the three numbers, not the arithmetic mean as Fred guessed. But that runs into the same problem as what Fred went on to describe if two of the three numbers are the same. So just ask your teacher what it means.