4
\$\begingroup\$

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();
  }
}
\$\endgroup\$
6
  • \$\begingroup\$ Does this order (sort) 1, 0, -1, 0? \$\endgroup\$
    – greybeard
    Commented May 11, 2023 at 10:21
  • \$\begingroup\$ Are you intentionally removing duplicate values equal to the pivot? \$\endgroup\$ Commented May 11, 2023 at 14:10
  • \$\begingroup\$ Why are you using java.security.SecureRandom instead of java.util.Random? \$\endgroup\$ Commented May 11, 2023 at 14:11
  • \$\begingroup\$ @greybeard yes, it works fine [Quick Sorting... -1,0,0,1] \$\endgroup\$ Commented May 11, 2023 at 15:41
  • 1
    \$\begingroup\$ @AmalKrishnan Oh right oops, I just saw == < >, and didn't bother double-checking what was being compared. As for SecureRandom, I don't think you need it here, and it's probably much slower, but that's your decision. \$\endgroup\$ Commented May 11, 2023 at 17:40

4 Answers 4

7
\$\begingroup\$

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.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ On {The "spirit" of the algorithm is a subjective view, therefore it cannot be used as solid criteria for review. I will thus ignore that completely.} This is actually the crux of what I was trying to implement. A pivot is picked from a list as a basis to separate the list into two parts, one with elements less than the pivot, and one with elements greater than the pivot; this process happens recursively, and ultimately every element 'is pivoted into its appropriate position'; thus resulting in a sorted list. The code reads to the flow. \$\endgroup\$ Commented May 10, 2023 at 12:25
  • 1
    \$\begingroup\$ @AmalKrishnan: That description of your design philosophy should probably be part of the question; I'd recommend editing it in. (Not into the code block as comments, just as text.) \$\endgroup\$ Commented May 10, 2023 at 22:34
  • 2
    \$\begingroup\$ @AmalKrishnan: Here is an interesting paper that exactly explores the idea of what the "essence" of an algorithm is: cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf It talks about the Sieve of Eratosthenes, not QuickSort, but it is very applicable here, since with both QuickSort and the Sieve of Eratosthenes, the fact that the algorithm is in-place is an important part of its performance characteristics. \$\endgroup\$ Commented May 11, 2023 at 10:35
  • \$\begingroup\$ Interesting detail. I was looking into it: "Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort." cite:C.L. Foster, Algorithms, Abstraction and Implementation, 1992, ISBN 0122626605, p. 98. I interpreted the partitioning scheme in a way that allows for more clarity. Using the same array tends to make the code very 'painful' to read. \$\endgroup\$ Commented May 11, 2023 at 15:29
  • \$\begingroup\$ You could resort to how Hoare presented the algorithm: separate partition from sort. \$\endgroup\$
    – greybeard
    Commented May 17, 2023 at 9:27
6
\$\begingroup\$

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.
\$\endgroup\$
5
  • \$\begingroup\$ 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(</>), and recursively repeats the process. Too many lists: yes, but for code readability and JVM does optimizations? \$\endgroup\$ Commented May 11, 2023 at 5:34
  • 1
    \$\begingroup\$ @AmalKrishnan This is far, far beyond the ability of any compiler or JVM implementation to optimize back to anywhere near the performance of a more standard quicksort implementation. The difference between reordering list elements in place vs copying them into separate lists is too fundamental. \$\endgroup\$
    – Douglas
    Commented May 11, 2023 at 6:19
  • 2
    \$\begingroup\$ @AmalKrishnan I consider your description of the Quick Sort algorithm to be critically incorrect in an essential detail. Quick Sort does not split the list elements into two lists. Quick Sort splits the list elements into two contiguous regions within the original (reordered) list. The fact that those two regions are within the original list is a very important part of how the algorithm achieves the "Quick" trait it is named for. \$\endgroup\$
    – Douglas
    Commented May 11, 2023 at 6:25
  • \$\begingroup\$ Interesting detail. I was looking into it: "Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort." cite:C.L. Foster, Algorithms, Abstraction and Implementation, 1992, ISBN 0122626605, p. 98. I interpreted the partitioning scheme in a way that allows for more clarity. Using the same array tends to make the code very 'painful' to read. \$\endgroup\$ Commented May 11, 2023 at 15:28
  • 1
    \$\begingroup\$ @AmalKrishnan The term "sub-array" in what you quoted specifically refers to segments of the original array that are still part of the array, not copied from it. Using the same array is an essential part of the algorithm's design. If you want to write code that improves clarity for that, you need to create a representation of the partitions that still uses the same underlying array for its internal storage. \$\endgroup\$
    – Douglas
    Commented May 11, 2023 at 18:50
2
\$\begingroup\$

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,1 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.


1 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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ What exactly would be slice one List into two subLists here? \$\endgroup\$
    – greybeard
    Commented May 17, 2023 at 9:29
  • \$\begingroup\$ @greybeard It means you would write the function to take a List<E>, an interface which both ArrayList and sublists implement, and call its subList method twice. \$\endgroup\$
    – Davislor
    Commented May 17, 2023 at 13:22
  • \$\begingroup\$ I can see how to do mergesort that way. What does it help with quicksort? \$\endgroup\$
    – greybeard
    Commented May 17, 2023 at 18:20
  • \$\begingroup\$ @greybeard The quicksort algorithm calls itself recursively on a pair of sub-arrays, one consisting of elements lower than the pivot, the other of elements higher than the pivot. If these are views, the algorithm runs in-place. This implementation currently creates lowerList and upperList, initialized to new ArrayList<Integer>() and inserts, rather than swapping in place. One using subList would need to track the final position of the pivot as it swaps, and partition afterward. \$\endgroup\$
    – Davislor
    Commented May 17, 2023 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.