6
\$\begingroup\$

I want my QuickSort class to have a static sort method that sort any List for any object that extends Comparable. Have I coded my class correctly? Can I make the use of generics a bit cleaner or is this the only way to code the signatures of the methods?

import java.util.List;

public class QuickSort{

    private QuickSort() {
        // prevent instantiation
    }

    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        quickSort(list, 0, list.size());
    }

    private static <T extends Comparable<? super T>> void quickSort(List<T> array, int start, int arrayLength){
        if(start < arrayLength){
            int q = partition(array, start, arrayLength);
            quickSort(array, start, q);
            quickSort(array, q+1, arrayLength);
        }
    }

    private static <T extends Comparable<? super T>> int partition(List<T> array, int end, int arrayLength){
        T last = array.get(arrayLength-1);
        int i = end-1;
        for(int j = end; j < arrayLength-1; j++){
            if(array.get(j).compareTo(last) <= -1 || array.get(j).compareTo(last) == 0){
                i = i+1;
                exchange(j, i, array);
            }
        }
        exchange(arrayLength-1, i+1, array);
        return i + 1;
    }

    private static <T extends Comparable<? super T>> void exchange(int j, int i, List<T> array){
        T temp = array.get(j);
        array.set(j, array.get(i));
        array.set(i, temp);
    }
}
\$\endgroup\$
8
\$\begingroup\$

Naming

QuickSort is not a simple algorithm, and naming things helps to make it more readable. Unfortunately, with descriptive names, if you name things wrong it makes it worse than if you you use cryptic names. Your recursive method is:

private static <T extends Comparable<? super T>> void quickSort(List<T> array, int start, int arrayLength){
    if(start < arrayLength){
        int q = partition(array, start, arrayLength);
        quickSort(array, start, q);
        quickSort(array, q+1, arrayLength);
    }
}

But, arrayLength does not mean array length, it means "end-exclusive", or "ignore-from" or something.

One of the common tricks in the quickSort is to use the actual index of the last element in the partition, instead of the length. For example, you call the method with:

quickSort(list, 0, list.size());

But, what if you called it with:

quickSort(list, 0, list.size() - 1);

Then named your parameters:

    private static <T extends Comparable<? super T>> void quickSort(
            List<T> array, int start, int end) {

Now you have start and end, and you do not need to do the immediate offset adjustment in the partition method.

Now, with that simple adjustment, the code becomes more readable simply because the variables do what they say, and don't lie to you.

Exchange

Your exchange method is good, no major problems there (with some caveats though... we will get to those...)

exchange is a decent name, but convention would call it swap...., give it decent index names, and common convention would be to put the indices after the reference:

private static <T extends Comparable<? super T>> void exchange(
        List<T> array, int left, int right) ....

Partitioning

Note, your current partition method is:

private static <T extends Comparable<? super T>> int partition(List<T> array, int end, int arrayLength){
    T last = array.get(arrayLength-1);
    int i = end-1;
    for(int j = end; j < arrayLength-1; j++){
        if(array.get(j).compareTo(last) <= -1 || array.get(j).compareTo(last) == 0){
            i = i+1;
            exchange(j, i, array);
        }
    }
    exchange(arrayLength-1, i+1, array);
    return i + 1;
}

Notice what happens if we give it decent variable names, and use the 'end' instead of the arrayLength

private static <T extends Comparable<? super T>> int partition(
        List<T> array, int first, int last) {
    T key = array.get(last);
    int smaller = first - 1;
    for (int test = first; test < last; test++) {
        if (array.get(test).compareTo(key) <= 0) {
            smaller++;
            exchange(smaller, test, array);
        }
    }
    smaller++;
    exchange(last, smaller, array);
    return smaller;
}

For a start, notice the condition:

if (array.get(test).compareTo(key) <= -1
        || array.get(test).compareTo(key) == 0) {

can be reduced to just:

if (array.get(test).compareTo(key) <= 0) {

All values up to smaller are smaller or equal to key.

Your code makes some sense to me now.

Note, the algorithm you use to partition the data is a little unconventional... though I can't see a real problem with it.

A conventional approach would have a left and right index that progress from the ends, and then swap values from each side, and meet in the middle somewhere. Your approach is OK, though.

Putting it together

With these changes, putting it all together, you will need to change the calling routines:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    quickSort(list, 0, list.size() - 1);
}

private static <T extends Comparable<? super T>> void quickSort(List<T> array, int left, int right){
    if(left  >= right) {
        return;
    }

    int q = partition(array, left, right);
    quickSort(array, left, q - 1);
    quickSort(array, q + 1, right);
}


private static <T extends Comparable<? super T>> int partition(
        List<T> array, int first, int last) {
    T key = array.get(last);
    int smaller = first - 1;
    for (int test = first; test < last; test++) {
        if (array.get(test).compareTo(key) <= 0) {
            smaller++;
            exchange(smaller, test, array);
        }
    }
    smaller++;
    exchange(last, smaller, array);
    return smaller;
}

private static <T extends Comparable<? super T>> void exchange(int j,
        int i, List<T> array) {
    T temp = array.get(j);
    array.set(j, array.get(i));
    array.set(i, temp);
}

public static void main(String[] args) {
    List<String> data = new ArrayList<String>(System.getProperties().stringPropertyNames());
    sort(data);
    for (String d : data) {
        System.out.println(d);
    }
}

Foot Notes

Note that your code has horrible performance on List instances that are not random-access... Consider someone who feeds your code a LinkedList... it will perform badly because each time you get or set with an index, it has to scan the data for the value.

RandomAccess is an interface available on collections that support fast and easy index-based access.

The Java implementation solves sorting non-RandomAccess Lists by dumping all the data in to a different RandomAccess list, sorting that, and then copying it back again, something like:

if (list instanceof RandomAccess) {
    sort(list);
} else {
    List<T> toSort = new ArrayList<>(list);
    sort(toSort);
    list.clear();
    list.addAll(toSort);
}
\$\endgroup\$
4
\$\begingroup\$

This looks pretty good, but there are a few things you can improve.

First, you should use descriptive names:

void exchange(int j, int i, List<T> array)

What do i and j mean here? This method uses good naming:

int partition(List<T> array, int end, int arrayLength)

Second, you should always put spaces around your operators, like this:

exchange(arrayLength - 1, i + 1, array);

Third, this is a bit redundant:

 i = i+1;
 exchange(j, i, array);

You could turn i = i + 1 into i++ or ++i, but you could also combine the statements like this:

exchange(j, ++i, array);

Be sure to use ++i in this case because a prefixed ++ or -- will cause that section of the statement to be evaluated first, while a suffixed ++ or -- will cause i to be incremented after the function call.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.