Quick Sort Done Lucidly

Question

I've been away from Programming and the Tech Industry for sometime. I thought I'd look at and try some of the older basic stuff. I bushed up to QuickSort and found most existing implementations of it, in Texts and on the web, to be a little convoluted. So I tried to simplify the implementation to be more in line with the spirit of the algorithm. Let me know your thoughts.

Design Philosophy: I interpreted/implemented Bubble Sort with the 'vibe' that the sort produces, and quick sort with its 'vibe' as well: the vibe that comes from a direct interpretation of the algorithm into code. As in, this is how i'd describe Quick Sort in implementation, without the 'high' or 'low', really distilling down to what i see as: a sorting algorithm that pivots an element into place and splits the rest of the elements into two lists based on whether the rest of the values are lesser or greater than the pivot, and recursively repeats the process. I want to avoid the normally available code that 'feels' disjoint from the essence of the algorithm.

package com.progint;

import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.SecureRandom;


public class QuickSortenDine {

  private ArrayList<Integer> listToSort;
  private ArrayList<Integer> sortedList;
  private SecureRandom pivotPicker; /*We're going to pick a Random pivot*/
    
  public QuickSortenDine() {
      listToSort =  new ArrayList<Integer>();
      sortedList = new ArrayList<Integer>();
      pivotPicker = new SecureRandom();
  }
  
  void quickSort() {
      quickSort(listToSort);
  }
  
  void quickSort(ArrayList<Integer> currentList) {
      int listSize = currentList.size();
      if (listSize == 1) sortedList.add(currentList.get(0));
      if (listSize <= 1) return;
      int low = 0 , high = listSize;
      int pivot = pivotPicker.nextInt(listSize);

      ArrayList<Integer>  lowerList = new ArrayList<Integer>();
      ArrayList<Integer>  higherList = new ArrayList<Integer>();
      int pivotValue = currentList.get(pivot);
      
      int currentIndex = low;
      while (currentIndex < high) {
          if (currentIndex == pivot) {currentIndex++; continue;}
          int currentElement = currentList.get(currentIndex++);
          if (currentElement < pivotValue) {lowerList.add(currentElement);}
          else/************* > **********/ {higherList.add(currentElement);}
      }
      quickSort(lowerList); sortedList.add(pivotValue); quickSort(higherList); 
  }
  
  public void readListToBeSorted() throws IOException {
      int len;
      BufferedReader consoleReader = new BufferedReader(new InputStreamReader(System.in));
      System.out.println("Enter the size of the List: ");
      len = Integer.parseInt(consoleReader.readLine());
      if (len<=0) {System.out.println("\nQuitting"); System.exit(0);}
      System.out.println("Enter the numbers: ");
      for (int i=0; i<len; i++) {
          int number;
          try {
              number = Integer.parseInt(consoleReader.readLine());
          }
          catch (NumberFormatException ne) {
              System.out.println("\nEnter Numbers Only\n");
              i--;
              continue;
          }
          listToSort.add(number);
          System.out.println();
      }  
  }
  
  void printList() {
      for (int i=0; i<sortedList.size(); i++) {
          System.out.print(sortedList.get(i));
          if (i==sortedList.size()-1) continue;
          else System.out.print(",");
      }
  }
  
  public static void main(String args[]) throws IOException {
      QuickSortenDine quickEn = new QuickSortenDine();
      quickEn.readListToBeSorted();
      System.out.println("\nQuick Sorting...");
      quickEn.quickSort();
      quickEn.printList();
  }
}

Answer 1

The "spirit" of the algorithm is a subjective view, therefore it cannot be used as solid criteria for review. I will thus ignore that aspect completely.

First and foremost, the algorithm dies with unnecessary memory allocation. I have never seen a quicksort that didn't perform its modifications within the given input list. If you have a source data of 4 elements, your algorithm creates 7 temporary ArrayList objects, each of which allocates one Integer[] object. None of the ArrayLists you create have a pre-defined initial size, so if you have a lot of data and the sublist were longer than 16 elements (that number varies between Java implementations) you end up also reallocating and copying data. For a few hundred elements this is unnoticeable but if you have millions of elements, the allocations degrade performance noticeably. Look into java.util.Collections.swap(List, int, int).

You should implement your algorithm as a reusable library that uses generic types so that it can take any List<T> and delegate the comparison implementation to a similarly provided Comparator<T>. Something like:

public class QuickSort {
    public static <T> void sort(List<T> list, Comparator<T> comparator) {
        ...
    }
}

You should decide whether you want to use curly braces in single line if-statements or not and stick with it. Code should be stylistically consistent so that whoever reads it doesn't need to adjust themselves to a new indentation style every few lines. I would advise with "use curly braces always", because then you don't have special cases when there more than one line in the code block, but it is a bit of a personal preference. Whatever you decide, never do this:

if (currentElement < pivotValue) {lowerList.add(currentElement);}

It doesn't make your code more readable and it is against all common Java coding conventions.

Don't try to condense your code by putting multiple statements on a single line. It is a code smell for a method that is too long. Also, as it does not follow any common coding conventions, it is thus hard to read.

Answer 2

Considering that the very name of the algorithm references speed, I think any approach that ignores important performance factors is very much against the "spirit" of the algorithm. As such, you should absolutely not be needlessly creating additional lists and copying list elements into them. To be a proper implementation of quicksort, following the spirit of the algorithm, the sorting must be done in place in a high performance manner. In order to do that, the recursive part of the method must take as parameters the index bounds of the region within the List to sort, instead of taking a separately built List. Since these superfluous performance-draining sublist copies are also the only reason for having the List itself in the parameters, the List should not be a method parameter.

The signature of your sorting method should therefore be void quickSort(int low, int high).

The separation of the list into parts is properly done by starting with a pair of empty regions at the two ends of the list, and growing the regions until they meet at the pivot. The regions are strictly conceptual, not separate lists, and are tracked in code only by tracking their boundary indexes as they grow.

In conceptual terms, the regions are grown by the following algorithm:

1. For each region:
   1. Check the element at the boundary of the region. If it belongs in that region, then move the boundary to include it.
   2. Repeat until you find an element at the region boundary that does not belong in that region.
2. If the region boundaries have met, then you're done with the pivot and separation and it's time to recurse.
3. Otherwise, having found elements at the boundaries of each region that each belong in the other region, swap those two elements. Then loop back to step 1.

Answer 3

To cover a few points that are not mentioned in the other two answers:

Choice of loops

Let's take a look at this while-loop:

      int currentIndex = low;
      while (currentIndex < high) {
          if (currentIndex == pivot) {currentIndex++; continue;}
          int currentElement = currentList.get(currentIndex++);
          if (currentElement < pivotValue) {lowerList.add(currentElement);}
          else/************* > **********/ {higherList.add(currentElement);}
      }

When you find yourself writing a while-loop where you have to increment an index on every single pass, that is a sign that you should be writing a for-loop or a foreach-loop instead.

The risk of every while-loop is that you could accidentally mess up and write a loop that runs forever, and the compiler won't yell at you. You can't make that mistake with a for-loop.

Here's an example for-loop to replace that while-loop:

for (int i = 0; i < listSize; i++) {
    if (i == pivot) {
        continue;
    }
    int currentElement = currentList.get(i);
    if (currentElement < pivotValue) {
        lowerList.add(currentElement);
    } else {
        higherList.add(currentElement);
    }
}

On the other hand, if you find yourself un-incrementing an index in the middle of your for-loop (as you do in your readListToBeSorted() method), then that's also a sign that something is off.

In your case, I would put a while-loop inside that for-loop. Conceptually, the while-loop's job is to keep asking the user for an input until it gets a valid one (a common use case for while-loops), and the for-loop's job is to control how many valid inputs are needed.

for (int i = 0; i < len; i++) {
    int number;
    while (true) {
        try {
            number = Integer.parseInt(consoleReader.readLine());
            break;
        } catch (NumberFormatException ne) {
            System.out.println("\nEnter Numbers Only\n");
        }
    }
    listToSort.add(number);
    System.out.println();
}

Choice of RNG

As mentioned by Solomon Ucko in a comment, java.security.SecureRandom is slower than java.util.Random. You probably don't need cryptographic security for this use case,¹ so for performance reasons, java.util.Random would be preferable.

(Of course, you are taking a larger performance hit from not sorting in-place, but you have made it clear that you are prioritizing the "legibility" of the algorithm over its speed.)

Indentation

This is a small style detail, but I thought I'd mention it.

The first level of indentation in your code is two spaces, while the deeper levels are all four spaces. Convention is to pick a single indentation style (e.g. two spaces, four spaces, tabs) and use it throughout the project.

In general, code style is something that you can configure your IDE to handle for you, and then stop thinking about.

---

¹ The risk with java.util.Random is that an attacker could observe a handful of outputs, work backwards to find the seed value, and then work forward to figure out the future outputs of the object.

For a quicksort implementation, if the attacker could figure out the seed value on a running system, they would know which pivots would be picked in the future. Then, they could supply a list that was specifically ordered so that the picked pivot value was always the worst one (i.e. always towards one extreme of the range of values), which would slow down the sort considerably.

But the risk of this happening in practice is, I think, rather low. First, the attacker cannot directly observe which pivots the code picks; they would have to deduce the pivots through timing attacks. Second—and more importantly—if the attacker can feed the quicksort code a new list to sort whenever they want, then they probably have better ways of slowing the system down anyway.

But I'm not a cybersecurity expert, so I could be wrong.

Answer 4

Sort Generic Lists

It’s even more in the spirit of the algorithm, as I see it, to sort a List of a generic type by a comparator. This is an interface that ArrayList implements.

In particular, that lets you slice the original ArrayList into two subList and recurse on them. That will massively improve your performance, since subList returns a view instead of copying the elements..