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:
- Should pointers be allowed to go beyond the pivot?
- What should happen if one pointer finds an element to swap, but the other doesn’t?
Eventually, I answered those questions as follows:
- Yes.
- 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:
- Out of bounds exceptions.
- Stack overflow errors.
- (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)