How can I fix the issue in quick sort algoritm in Java

Question

I have a problem about sorting object array thanks to quick sort algorithm.

I created Person object including id, name, surname and lastly age.

I used comparator to sort list in terms of the attributes of person object.

Here is an example shown below.

Comparator<Person> compTr = new Comparator<Person>() {
    @Override
    public int compare(Person p0, Person p1) {
        return Long.compare(p0.getId(), p1.getId());
    }
};

I think my problem is located in both two while loop by implementing greaterthan and lessthan. Here is the problem I think

        while (lessThan(comp, array[i], pivot)) {
            i++;
        }
        while (greaterThan(comp, array[i], pivot)) {
            j--;
        }

How can I fix the problem.

I also added my algorithm to the post.

Here is my quick sort algorithm implementation code snippet

public static Person[] quickSort(Person a[], Comparator comp) {
    return quickSort(a, 0, a.length - 1, comp);
}

private static Person[] quickSort(Person[] array, int lowerIndex, int higherIndex, Comparator comp) {

    int ll = lowerIndex;
    int rr = higherIndex;

    if (rr > ll) {

        // calculate pivot number, I am taking pivot as middle index number
        Person pivot = array[(higherIndex - lowerIndex) / 2];

        while (ll <= rr) {
            while (ll < higherIndex && lessThan(comp, array[ll], pivot)) {
                ll += 1;
            }
            while (rr > lowerIndex && greaterThan(comp, array[rr], pivot)) {
                rr -= 1;
            }
            if (ll <= rr) {
                exchangeNumbers(array, ll, rr, comp);
                ll += 1;
                rr -= 1;
            }
        }
        if (lowerIndex < rr) {
            quickSort(array, lowerIndex, rr, comp);

        }
        if (ll < higherIndex) {
            quickSort(array, ll, higherIndex, comp);
        }
    }
    return array;
}

private static void exchangeNumbers(Person[] array, int i, int j, Comparator comp) {
    Person temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

// ASC
private static boolean greaterThan(Comparator comp, Person x, Person y) {
    return comp.compare(x, y) > 0;
}

// DESC
private static boolean lessThan(Comparator comp, Person x, Person y) {
    return comp.compare(x, y) < 0;
}

Answer 1

The simple answer is that you're calculating the index of the pivot element incorrectly. You want:

Person pivot = array[(higherIndex + lowerIndex) / 2];

with a + not a -.

Or:

Person pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];

But honestly I'm not a fan of this quicksort strategy. It does weird things like swap elements with themselves (when ll == rr) and leave elements equal to the partition value on both sides of the partition. There's a better way.