Adding extra sort criteria in quick sort in java

Question

So i have this code to quick sort a list of students by grade.

public static void quickSort(Student[] school){
    quickSort(school, 0, school.length - 1);              // quicksort all the elements in the array
}

private static void quickSort(Student[] school, int start, int end) {
    int i = start;                          // index of left-to-right scan
    int k = end;                            // index of right-to-left scan

    if (end - start >= 1) // check that there are at least two elements to sort
    {
        Student pivot = school[start];       // set the pivot as the first element in the partition

        while (k > i) // while the scan indices from left and right have not met,
        {
            while (school[i].getStudentGrade() <= pivot.getStudentGrade() && i <= end && k > i) // from the left, look for the first
            {
                i++;
                                                   // element greater than the pivot
            }
            while (school[k].getStudentGrade() > pivot.getStudentGrade() && k >= start && k >= i) // from the right, look for the first
            {
                k--;                                        // element not greater than the pivot
            }
            if (k > i) // if the left seekindex is still smaller than
            {
                swap(school, i, k);                      // the right index, swap the corresponding elements
            }
        }
        swap(school, start, k);          // after the indices have crossed, swap the last element in
        // the left partition with the pivot 
        quickSort(school, start, k - 1); // quicksort the left partition
        quickSort(school, k + 1, end);   // quicksort the right partition
    } else // if there is only one element in the partition, do not do any sorting
    {
        return;                     // the array is sorted, so exit
    }
}

//Swap 2 index values in array
private static void swap(Student[] school, int index1, int index2)
{
    Student temp = school[index1];           
    school[index1] = school[index2];    
    school[index2] = temp;               
}

I only can't figure out how to add an extra sort criteria so students with the same grade are sorted based on there student number which i get by using student.getStudentNumber.

One way is to abstract your comparison into a separate method. This way, your sorting algorithm doesn't have to change just because you're changing the sort criteria. One typical approach is to have the sorting method return one of {-1,0,1}, depending on whether the first argument is less than, equal to or greater than the second argument. — Andy Thomas
@AndyThomas: That's exactly the solution. Add that as an answer, with an example. I'll upvote it. — Jim Mischel

MrSmith42 MrSmith42 · Accepted Answer · 2015-11-11T14:10:23

Instead of directly using a compare function, pass a java.util.Comparator<T>. This way you can implement different Comparators for different sort criteria.

The comparator would look like this:

import java.util.Comparator;

public class StudentComparator implements Comparator<Student> {

    @Override
    public int compare(final Student s1, final Student s2) {
        final int gradeDiff = s1.getStudentGrade() - s2.getStudentGrade();
        if (0 != gradeDiff) {
            return gradeDiff;
        }
        final int numberDiff = s1.getStudentNumber() - s2.getStudentNumber();
        if (0 != numberDiff) {
            return numberDiff;
        }
        // addd mor criteria here if wanted
        return 0;
    }
}

Adding extra sort criteria in quick sort in java

2 Answers