# There's something wrong with my quicksort. What exactly?

As an exercise, I wrote a class called `Sorter` that sorts arrays of ints according to several common sorting algorithms. I implemented multiple algorithms, including the merge sort, but I struggle to implement the quicksort algorithm. I debugged it for many, many hours to no avail. Some questions I had in mind while implementing the algorithm:

1. Should pointers be allowed to go beyond the pivot?
2. What should happen if one pointer finds an element to swap, but the other doesn’t?

Eventually, I answered those questions as follows:

1. Yes.
2. Nothing.

I’m not sure my answers are correct. At any rate, there’s some mistake lurking in the code that I can’t pinpoint. At different points, I got:

1. Out of bounds exceptions.
2. Stack overflow errors.
3. (currently) Logical errors (that is, the results are not correct)

Even a good sleep didn’t help. Nothing helps. Can you help me?

``````public class Sorter {
private static final Sorter instance = new Sorter();

private Sorter() {
}

public static Sorter getSorter() {
return instance;
}

// other algorithms

public int[] quicksort(int[] arr) {
int[] arrCopy = Arrays.copyOf(arr, arr.length); // so that the function is pure
quicksort(arrCopy, 0, arr.length);
return arrCopy;
}

private void quicksort(int[] arr, int lowIndex, int highIndex) { // as per convention, the lowIndex is inclusive, whereas the highIndex is exclusive (think substring(), copyOfRange(), etc.)
if (highIndex - lowIndex < 2) { // base condition
return;
}
int pivotIndex = randomInt(lowIndex, highIndex); // equivalent to (int) (Math.random() * (highIndex - lowIndex) + lowIndex)
int leftPointer = lowIndex - 1, rightPointer = highIndex;
int leftElementToSwapIndex, rightElementToSwapIndex;
while (leftPointer < rightPointer) {
leftElementToSwapIndex = rightElementToSwapIndex = -1;
while (leftPointer < rightPointer && leftPointer < highIndex - 1) {
leftPointer++;
if (arr[leftPointer] > arr[pivotIndex]) {
leftElementToSwapIndex = leftPointer;
break;
}
}
while (rightPointer > leftPointer) {
rightPointer--;
if (arr[rightPointer] < arr[pivotIndex]) {
rightElementToSwapIndex = rightPointer;
break;
}
}
if (leftElementToSwapIndex != -1 && rightElementToSwapIndex != -1) { // swap if both pointers found something to swap
ArrayUtils.swap(arr, leftElementToSwapIndex, rightElementToSwapIndex); // the class is from Apache Commons, it works fine
}
}
ArrayUtils.swap(arr, leftPointer, pivotIndex); // swap the element both pointers point at and the pivot
quicksort(arr, lowIndex, leftPointer);
quicksort(arr, leftPointer + 1, highIndex);
}
}
``````
``````public class SorterTest {
private final Sorter sorter = Sorter.getSorter();

private static final int DEFAULT_ARRAY_LENGTH = 100_000;

// other tests, they pass

@Test
public void testQuicksort() { // it should pass
int[] arr = getIntArray();
assertArrayEquals(getSortedArray(arr), sorter.quicksort(arr));
}

private int[] getIntArray() { // I don't like to pass defaults
return getIntArray(DEFAULT_ARRAY_LENGTH);
}

private int[] getIntArray(int length) {
int[] arr = new int[length];
for (int i = 0; i < length; i++) {
arr[i] = randomInt(); // the same randomInt() as in the quicksort() method, only with reasonable defaults, 0 and 1000
}
return arr;
}

private int[] getSortedArray(int[] arr) { // pure
int[] sortedArr = Arrays.copyOf(arr, arr.length);
Arrays.sort(sortedArr);
return sortedArr;
}
}
``````

Please keep in mind that I’m not as interested in how to write a working quicksort as in what exactly I did wrong in my implementation (and how I can fix it with as few changes as possible)

You can set a debugger on this.

If you have a small list for example you can hand trace what you think your code should do (you already have a good grasp on that).

The debugger will allow you to jump to specific iterations to and where your expectation and the code diverge you can pinpoint what’s wrong.

1 Like

I watched the relevant [Coding With John video][1] (I didn’t want to, but I was desperate). For some reason, he swapped the pivot with the last element first thing and only then did the partitioning. I repeated it, and now it works. I don’t know why the pivot has to be the last element, but it does

``````    private void quicksort(int[] arr, int lowIndex, int highIndex) {
if (highIndex - lowIndex < 2) {
return;
}
int pivotIndex = Util.randomInt(lowIndex, highIndex);
int pivot = arr[pivotIndex];
ArrayUtils.swap(arr, pivotIndex, highIndex - 1); // notice this change
int leftPointer = lowIndex - 1, rightPointer = highIndex;
int leftElementToSwapIndex, rightElementToSwapIndex;
while (leftPointer < rightPointer) {
leftElementToSwapIndex = rightElementToSwapIndex = -1;
while (leftPointer < rightPointer && leftPointer < highIndex - 1) {
leftPointer++;
if (arr[leftPointer] > pivot) {
leftElementToSwapIndex = leftPointer;
break;
}
}
while (rightPointer > leftPointer) {
rightPointer--;
if (arr[rightPointer] < pivot) {
rightElementToSwapIndex = rightPointer;
break;
}
}
if (leftElementToSwapIndex != -1 && rightElementToSwapIndex != -1) {
ArrayUtils.swap(arr, leftElementToSwapIndex, rightElementToSwapIndex);
}
}
ArrayUtils.swap(arr, leftPointer, highIndex - 1);
quicksort(arr, lowIndex, leftPointer);
quicksort(arr, leftPointer + 1, highIndex);
}
``````

I hope it helps someone else who finds themselves in the same situation one day

One last thing to note, though. John in the aforementioned video managed to sort a ten-million-element array and got a `StackOverflowError` only when increasing it to one hundred million. I, on the other hand, get that error when dealing with just ten million elements (a million is fine). I wonder why it’s so…

Did you set up a debugger though?
Learning how to use a debugger is an invaluable tool. Without a debugger work would take infinitely more time (or good logging, if it’s not something that can be run in a traceable environment).