Is this quicksort efficient and acceptable?

Question

In order to complete one of my assignment I needed to include a quicksort so I was wondering if this is correct and acceptable.

The code:

    private ArrayList<String> sort(ArrayList<String> ar, int lo, int hi){
        if (lo < hi){
            int splitPoint = partition(ar, lo, hi);
            sort(ar, lo, splitPoint);
            sort(ar, splitPoint +1, hi);
        }
        return ar;
    }

    private int partition(ArrayList<String> ar, int lo, int hi){
        String pivot = ar.get(lo);
        lo--;
        hi++;
        while (true){
            lo++;
            while (lo<hi && ar.get(lo).compareTo(pivot) < 0){
                lo++;
            }
            hi--;
            while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){
                hi--;
            }
            if (lo<hi){
                swap(ar, lo, hi);
            }else {
                return hi;
            }
        }
    }

The additional swap method:

    private ArrayList<String> swap(ArrayList<String> ar, int a, int b){
        String temp = ar.get(a);
        ar.set(a, ar.get(b));
        ar.set(b, temp);
        return ar;
    }

If this is incorrectly done can you please give me some pointers and tell me why. Otherwise I would gladly accept any suggestions you have.

Answer 1

Those are pure functions that don't access any instance variables. You can therefore make them static.

You could use generics more generically. Your code should work with any List, as long as it supports an efficient .get(i) for arbitrary i. The elements of the list can be any kind of Comparable object.

The .sort() function should have a void return type to avoid giving the false impression that it returns a copy of the original array.

private static <E extends Comparable<E>, L extends List<E> & RandomAccess>
void sort(L ar, int lo, int hi) {
    if (lo < hi) {
        int splitPoint = partition(ar, lo, hi);
        sort(ar, lo, splitPoint);
        sort(ar, splitPoint +1, hi);
    }
}

private static <E extends Comparable<E>, L extends List<E> & RandomAccess>
int partition(L ar, int lo, int hi){
    E pivot = ar.get(lo);
    lo--;
    hi++;
    while (true){
        lo++;
        while (lo<hi && ar.get(lo).compareTo(pivot) < 0){
            lo++;
        }
        hi--;
        while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){
            hi--;
        }
        if (lo<hi){
            swap(ar, lo, hi);
        }else {
            return hi;
        }
    }
}

private static <E extends Comparable<E>, L extends List<E> & RandomAccess>
void swap(L ar, int a, int b){
    E temp = ar.get(a);
    ar.set(a, ar.get(b));
    ar.set(b, temp);
}

Answer 2

I agree with the handy generics use from previous answer and I would like to add something more that I noticed.

In your partition method I thin you can remove the following code

private int partition(ArrayList<String> ar, int lo, int hi){
    String pivot = ar.get(lo);
    lo--;//remove
    hi++;//remove
    while (true){
        lo++;//remove
        while (lo<hi && ar.get(lo).compareTo(pivot) < 0){
            lo++;
        }
        hi--;//remove
        while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){
            hi--;
        }
        if (lo<hi){
            swap(ar, lo, hi);
        }else {
            return hi;
        }
    }
}

I the l-- and l++ right after you can get rid of because this path always happens. regarding the h++ and h-- I had to look into it longer but if you think line by line what the code does I am pretty sure those two can be removed as well.

Efficiency:

Another important point regarding the efficiency (since you asked that as well) is the selection of the pivot. Quick sort has complexity from O(n.logn) to O(n^2). And that depends on the selection of the pivot. Lets say you try to sort the array that is sorted other way around. Your pivot selection would result in O(n^2) complexity because in every level of recursion one half is of a size of 1 and other is n - 1. The best complexity would be if both the half are the same at each level, which you cannot achieve for any array.

Statistically speaking if you select the pivot randomly every time you end up with asymptotic time complexity O(nlogn) in most of the cases. That is why Quicksort is said to have average time complexity O(nlogn).

Last addition about the static method. That was a good point in the previous answer but just bear in mind that static methods cannot be overriden and are hard to mock in testing. So if you would like to do some general design of your classes to let's say have one super class "Sort" with method sort and underneath having QuickSort, Buble, Merge Sort... you would probably like to stay with non-static sorting method.