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
Thanks guys
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.
}
}