I need help working out a partitioning method. On my method, an int[] array of [
ID: 3593740 • Letter: I
Question
I need help working out a partitioning method. On my method, an int[] array of [2, 9, 3, 7, 8, 6, 4], which is supposed to be sorted as [6, 4, 3, 2, 7, 8, 9] had come out as [4, 6, 8, 3, 2, 9, 7]. I have added code for my partition method below, and I would appreciate a reworked version of my code as an answer. Thanks!
public static <T> int partition (T[] data, int startPos, int endPos, Comparator<T> comparator)
{
int pivotPos = (int) Math.floor((startPos + endPos) / 2);
T pivotElement = data[pivotPos];
T tempElement = pivotElement;
data[pivotPos] = data[startPos];
data[startPos] = tempElement;
/* The remaining elements are partitioned into smaller and then larger
* elements in a single pass (using the standard partition algorithm).
*/
while (startPos <= endPos)
{
while (comparator.compare(data[endPos], pivotElement) > 0)
{
endPos--;
comparisonCount++;
}
while (comparator.compare(data[startPos], pivotElement) < 0)
{
startPos++;
comparisonCount++;
}
if (comparator.compare(data[startPos], data[endPos]) > 0)
{
tempElement = data[startPos];
data[startPos] = data[endPos];
data[endPos] = tempElement;
endPos--;
startPos++;
}
}
// Swap pivot with right element
pivotPos = startPos;
tempElement = data[pivotPos];
data[pivotPos] = data[endPos];
data[endPos] = tempElement;
return endPos;
}
Explanation / Answer
// Swap pivot with right element
here instead pivotPos = startPos;
make pivotPos=0; Will get the required array.
As you are making pivotPos as startPos. and swapping, there is no difference b/w this swapping and the swapping done in above loop. Just making into same array. We have to swap the endPos i.e right element with the pivotElem, which is atr index 0. so make pivotPos as 0