2
\$\begingroup\$

I am looking for assistance in optimizing a partition method I wrote for a class. It does its job correctly, but I only received half points on it, so I was wondering if there was a way to make it more efficient?

private int runPartition(int lowIndex, int highIndex)
  {
     //Sets up pivot index and values
     int pivotIndex = lowIndex;
     int pivotValue = localArray[pivotIndex];

     //Inner counter value
     int counterOne = highIndex + 1;

     //Loops through array from top down
     for (int counterTwo = highIndex; counterTwo >= lowIndex; counterTwo--)
        {
           //If element is bigger than pivot, move to end
           if (localArray[counterTwo] > pivotValue)
              {
                 //Decrements inner counter and swaps values
                 counterOne--;
                 swapValuesAtIndex(counterTwo, counterOne);
              }
        }

     //At end, swap pivot value with value BEFORE larger elements
     counterOne--;
     swapValuesAtIndex(counterOne, pivotIndex);

     //Sets new pivot index and returns
     pivotIndex = counterOne;
     return pivotIndex;
  }
\$\endgroup\$
  • \$\begingroup\$ When you say "partition method", can you specify exactly what you mean to avoid any potential confusion? \$\endgroup\$ – Simon Forsberg Feb 24 at 14:57
  • \$\begingroup\$ Yes - this method partitions the array around the top index in the array. For example, for an array of {3, 9, 6}, the number 6 would be the partition index, and the other items would be sorted so that the numbers equal to or less than 6 would come before it, and the numbers greater than 6 would come after it. This method is used in a quick sort method. \$\endgroup\$ – Richard McCormick Feb 27 at 9:21
5
\$\begingroup\$

I'm wondering if it is the efficiency that resulted in you getting half points:

  • runPartition is rather an unclear name in itself;
  • highIndex seems to be inclusive, which is uncommon (the number of elements is now highIndex - lowIndex + 1);
  • counterOne and counterTwo are not good names for indices - even i and j would have been better;
  • it is very likely that the localArray as a field name raises some questions; why is it a field in the first place? And why is it called local if it is not local to the method?
  • it seems to me that you would set the counterOne to the index you want to swap and perform the decrease afterwards (possibly using -- in the call to swapValues);
  • the braces are at uncommon and uneven positions when it comes to Java / indentation.
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.