QuickSort in Java

Question

I've written my first implementation of quicksort in Java 8. Please let me know of any improvements that I can make (e.g. whether I'm creating any Lists unnecessarily).

Also, when I try to add elements directly to the leftArray, I get a ConcurrentModificationException. Doesn't subList() create a new List that's separate from the one that's passed into the sublist() method? (the stuff related to the ConcurrentModificationException is commented out. The code is working correctly.)

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

    public List<Integer> quickSort(List<Integer> arrayToSort){
        if(arrayToSort.size() <= 1){
            return arrayToSort;
        }

        int pivot = arrayToSort.get(0);
        int i = 0, j = 1;       // i is index of rightmost element with a value less than pivot's

        while(j < arrayToSort.size()){
            if(pivot > arrayToSort.get(j)){
                swap(i + 1, j, arrayToSort);
                i++;
            }
            j++;
        }
        swap(0, i, arrayToSort);

        List<Integer> leftArray = quickSort(arrayToSort.subList(0, i));
        List<Integer> rightArray = quickSort(arrayToSort.subList(i + 1, arrayToSort.size()));

        if(false){
            // Why do I get a ConcurrentModificationException here? Doesn't .subList() create a new list?
            //leftArray.add(arrayToSort.get(i));
            //leftArray.addAll(rightArray);
            //return leftArray;
        }
        List<Integer> sorted = new ArrayList<>(leftArray.size() + rightArray.size() + 1);
        sorted.addAll(leftArray);
        sorted.add(arrayToSort.get(i));
        sorted.addAll(rightArray);
        return sorted;
    }

    private void swap(int a, int b, List<Integer> arrayToSort){
        int temp = arrayToSort.get(a);
        arrayToSort.set(a, arrayToSort.get(b));
        arrayToSort.set(b, temp);
    }
}

Answer 1

One thing that you might consider changing is your choice of pivot. Choosing the first element is rather risky, as your code will perform poorly (closer to O(n^2) worst case of quicksort) for sorted/reverse sorted/nearly sorted data (which is actually fairly common in real world scenarios). This is because your partition will be very unbalanced, and so your stack will end up having height O(n) instead of O(log n).

A common pivot choice is "median of 3". Pick the first, middle and end elements and then choose the median value as your pivot. This choice will perform much closer to optimal O(n log n) runtime for arbitrary input.

This approach has a significant advantage over yours because multiple values are considered. This means that you will get a more representative sample of the data and so your pivot will better fit the data.

If you have access to a fast cryptographically secure random number generator (not Java's rand, though apparently SecureRandom seems to fit this criteria), then a very good choice for pivots is a random index, as then you will not suffer from O(n^2) performance on average, as probability dictates that it is extremely unlikely to choose many bad pivots consecutively. The RNG has to be secure as otherwise it is still possible to construct datasets that cause quick sort to regress to O(n^2) performance. The problem is that RNGs are usually slow, and so may not be worth the effort.

Answer 2

On the whole this looks great, just a few minor observations:

• Your code sorts the supplied list and also returns a sorted list. This seems a little confusing. Either you should return nothing (void) or you should take a copy of the input list and leave it unchanged.

  In case that wasn't clear, here's an example of what I mean:

  List<Integer> unsorted = Arrays.asList(1, 5, 6, 7, 2);
  List<Integer> sorted = quickSort(unsorted);
  
  System.out.println(unsorted);
  System.out.println(sorted);
  

  Here, both lists will print: [1, 2, 5, 6, 7].

• You have a while loop that seems like it could be a for-loop instead:

  int i = 0;                    
  
  for (int j = 1; j < arrayToSort.size(); j++) {
    if (pivot > arrayToSort.get(j)) {
      swap(i + 1, j, arrayToSort);
      i++;
    }
  }
  

  This is a very minor tweak, but it constrains j's scope to be within the loop, plus I think it reads more naturally.

• Both methods can be static, since there is no state contained within the class instance.

• You asked if you are using too many lists. Quicksort can be achieved in-place (i.e. within one array-like structure), so there is certainly scope for improvement in that regard, although probably at the cost of performance. But I certainly find your code easy to read (and thus maintain), which isn't a bad thing at all.