# QuickSort in Java with Lomuto Partition or Hoare Partition

Posted on

Problem

I have developed a quick sort in java, that can work with both Lomuto Partition Strategy, or Hoare Partition Strategy.

Both of them sort the array correctly.

I would like to have it code reviewed to ensure I was able to correctly implement each one of those partitioning strategies.

Is there any reason to use one vs the other?

Here it is:

``````public class QuickSort {

public static void main(String... args) {
int array[] = {2, 3, 4, 1, 11, 5, 7, 0, 10, -1, 99, 23};
quickSort(array);
System.out.println(Arrays.toString(array));
}

public static void quickSort(int array[]) {
quickSort(array, 0, array.length - 1);
}

private static void quickSort(int array[], int l, int r) {
if (l >= r) {
return;
}
int p = lomutoPartition(array, l, r);//hoarePartition(array, l, r);//lomutoPartition(array, l, r);
quickSort(array, l, p - 1);
quickSort(array, p + 1, r);
}

private static int lomutoPartition(int array[], int l, int r) {
//pivot chosen
int pivot = array[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, r);
return i + 1;
}

private static int hoarePartition(int array[], int l, int r) {
int pivot = array[r];
int left = l;
int right = r;
while (true) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left >= right) {
return left;
}
swap(array, left, right);
}
}

private static void swap(int array[], int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}

}
``````

Solution

``````public static void main(String... args) {
int array[] = {2, 3, 4, 1, 11, 5, 7, 0, 10, -1, 99, 23};
quickSort(array);
System.out.println(Arrays.toString(array));
}
``````

I like that you’re testing your code, but you have to visually verify your program’s correctness. It would be better to use a testing framework and automate that task.

``````private static void quickSort(int array[], int l, int r) {
``````

One letter variable names are hard to read.
It would be better to use `left` and `right` here.
Alternatively, `lhs` and `rhs` are common abbreviations for “left hand side” and “right hand side”.
I don’t care for them, but they’re common enough that I let them slide through code reviews at work.

``````   int p = lomutoPartition(array, l, r);//hoarePartition(array, l, r);//lomutoPartition(array, l, r);
``````

It happened because you’re physically changing the code in order to switch between your two different strategies.
It would be better to actually implement the strategy pattern.

You could create a `PartitioningStrategy` like this.

``````interface PartitioningStrategy {
int partition(int numbers[], int left, int right);
}
``````

And then have two implementations.

``````public class HoarePartitioningStrategy implements PartitioningStrategy {
public int partition(int numbers[], int left, int right) {
//...
}
}

public class LomutoPartitioningStrategy implements PartitioningStrategy {
public int partition(int numbers[], int left, int right) {
//...
}
}
``````

Then you can decide which strategy to use in your `main`.

``````public static void main(String... args) {
int array[] = {2, 3, 4, 1, 11, 5, 7, 0, 10, -1, 99, 23};
quickSort(array, new LomutoPartitioningStrategy());
System.out.println(Arrays.toString(array));
}
``````

Nice and clean. Keeps your code open for extension, but closed for modification.