2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Is your code actually working? Your comment about the ConcurrentModificationException suggests that it's not, which would make your question off-topic. \$\endgroup\$ – tim Mar 30 '15 at 20:26
  • 1
    \$\begingroup\$ Yes, my code works. The stuff related to the ConcurrentModificationException is in the if-statement that has a false value, so it's not executed by the JVM. \$\endgroup\$ – Calculus5000 Mar 30 '15 at 20:37
  • \$\begingroup\$ When in doubt, read the documentation - sublist creates a new list but it is backed by the original one. A change to one will change the other. \$\endgroup\$ – Simon Forsberg Mar 30 '15 at 22:06
  • \$\begingroup\$ @SimonAndréForsberg I've read the documentation and whilst I understand that the method becomes undefined if the original array is structurally modified, I don't think I’m doing that here. At any recursion level, elements are added from arrayToSort and rightArray to leftArray (all of which are sublists at a given recursion depth). Judging by what is said on the documentation, these structural modifications can be made as they're done via the returned sublist. I would expect to get a ConcurrentModificationException the original is structurally changed however. \$\endgroup\$ – Calculus5000 Apr 2 '15 at 16:49
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Great, thanks for this! I've implemented both the median of three and randomly choosing a pivot using SecureRandom, and I noticed that when I count the number of inversions, choosing a random pivot consistently results in a larger number of swaps. Does this makes the median of three the better choice of the two for this data set? If so, in what cases is it preferable to randomly choose a pivot over using the median of three? \$\endgroup\$ – Calculus5000 Apr 1 '15 at 12:08
  • 1
    \$\begingroup\$ A random pivot only helps to avoid worst case scenarios like people trying to sabotage your service by giving it a bad input. So in a consistency demanding environment, you would always go for a random pivot. You may also want to try multiple random pivots and again taking the median, as that should reduce the number of swaps. If your data set performs best with 1 method, then of course you should use that method. \$\endgroup\$ – mleyfman Apr 1 '15 at 15:46
  • 1
    \$\begingroup\$ Also, I don't think that counting swaps is a good measure of the number of operations. Quicksort relies on being able to do O(n) work per level and having O(lg n) levels. You could some sort of analysis based on the maximum height of the call stack. You can also see how far the partition deviates from the optimal 50/50 split for each call. \$\endgroup\$ – mleyfman Apr 1 '15 at 21:04
2
\$\begingroup\$

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.

\$\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.