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.

• Simon Forsberg: Have you tested your code anything?
• Cristian Gutu: @SimonAndréForsberg yes I did and it seems to work.

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);
}

• rolfl: I am not a fan of exposing the RandomAccess interface in the generics. In this case, as example code, it sort of makes sense, but, in a real implementation, the signature should just be private static <E extends Comparable<E>> void sort(List<E> ar, int lo, int hi) {... and then, inside the sort method, it should choose between two alternative algorithms depending on whether the input list is RandomAccess or not. The RandomAccess interface leads to confusion for most Java programmers (who have never heard of it).
• 200_success: @rolfl True, but then you would be getting into creeping expansion of feature scope. My point was that you could get that flexibility for free just by changing the method signatures.
• Cristian Gutu: It all seems reasonable points to me, but as of now I can't relate to what you said as I am still to learn 'generics' in my AP class.

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.