3
\$\begingroup\$

Dutch Partition problem. Partition the given array using the pivotIndex into groups with elements smaller than the pivot, equal to pivot and larger than the pivot.

public static void partition(int[] inputArray, int pivotIndex){
    int smaller = 0, equal = 0, larger = inputArray.length-1;
    int pivot = inputArray[pivotIndex];
    while(equal <= larger){
      if(inputArray[equal] < pivot){
        swap(inputArray, smaller, equal);
        smaller++;
        equal++;
      } else if(inputArray[equal] == pivot){
        equal++;
      } else {
        swap(inputArray, equal, larger--);
      }
    }
  }

private static void swap(int[] inputArray, int firstIndex, int secondIndex){
    int temp = inputArray[firstIndex];
    inputArray[firstIndex] = inputArray[secondIndex];
    inputArray[secondIndex] = temp;
  }
\$\endgroup\$
3
\$\begingroup\$

int smaller = 0, equal = 0, larger = inputArray.length-1;

I recommend to put every variable declaration on a separate line. (lmus said it in his answer already, but I find it much more important.)

int smaller = 0;
int equal = 0;
int larger = inputArray.length - 1;

It makes it much more readable. Especially when you are looking for a variable declaration, you find it way faster.


I don't think that the above variable names are particularly well chosen. These names look like boolean names. I don't know the algorithm well enough to suggest better names (the Wikipedia article for the algorithm uses single letters, which is certainly not better), but I don't know what smaller or larger or equal should mean, so I think there might be better names.

Also the name inputArray is redundant, because the type of a variable does not need to be in the name. numbers might be better, because it tells you what it contains, and also it is not important whether they are input (in the sense of user input) or not. In case you mean input to the algorithm, then that is clear by it being a parameter. Since it is a kind of sorting algorithm, numbersToSort might be good and more explicit. The latter also makes more clear that the numbers are sorted in place, while inputArray might deceive the caller to forget that it is also the output array.


int pivot = inputArray[pivotIndex];

I don't really see a value in saving this in a variable. The name makes it less explicit; without reading more code, you can't really know whether pivot is an index or the pivotElement (which might be a better name).

Since you access inputArray[equal] with the index as well, I would just remove the above variable and replace

if(inputArray[equal] < pivot){

with

if (inputArray[equal] < inputArray[pivotIndex])

Your use of spaces is inconsistent. For example, you have a space after the else before the brace, but not after the else if. I would usually put a space before every opening brace, and also after every if, else, while etc., as it makes the code look less pressed together, but it is most important to be consistent.


swap(inputArray, smaller, equal);
smaller++;
equal++;

and

swap(inputArray, equal, larger--);

is another inconsistency. You could either do swap(inputArray, smaller++, equal++); to be consistent, or the longer, more explicit and also consistent version of replacing the second one with

swap(inputArray, equal, larger);
larger--;

I would prefer the latter, more explicit variant.

\$\endgroup\$
0
\$\begingroup\$

Not much to add here. The code is written clearly. There are almost no style issues. (It's usually better to declare variables on separate lines but it's clear enough here to not be a real problem).

The only small thing I would change is renaming equal to current, but this could also be a preference thing. The current is better to indicate which element we're currently working with whereas the equal makes it obvious that there's a middle block of items that are equal to the pivot.

Well done.

\$\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.