Quicksort implementation in Java

Question

I wrote this implementation of quicksort as a bit of practice and review for myself. I did not base my algorithm on anything more than my own understanding of quicksort and working through a couple of examples myself on paper, so please let me know of any improvements or optimizations that I could make!

import java.util.ArrayList;
import java.util.Collections;
import java.util.concurrent.ThreadLocalRandom;

/**
 * A simple, generic, in-place implementation of quicksort
 * @implNote The pivot used during the partitioning step is selected at random
 */
public class Quicksort {

    /**
     * Sort the given array using quicksort
     * @param arr Array to sort
     * @param <E> Type of the elements contained by arr
     */
    public static <E extends Comparable> void sort(ArrayList<E> arr) {
        sort(0, arr.size() - 1, arr);
    }

    /**
     * Sorts a designated section of the given array using quicksort
     * @param left  Lower-bound index of section (inclusive)
     * @param right Upper-bound index of section (inclusive)
     * @param arr   Array to perform sort within
     * @param <E>   Type of the elements contained by arr
     */
    private static <E extends Comparable> void sort(int left, int right, ArrayList<E> arr) {
        // Exit if section contains only a single element, or is invalid
        if (right - left < 1) {
            return;
        }

        // Select a pivot at random
        int pivot = ThreadLocalRandom.current().nextInt(left, right + 1);

        // Partition this section of the array
        int pivotFinalIndex = partition(left, right, pivot, arr);

        // Sort the two new partitions
        sort(left, pivotFinalIndex - 1, arr);
        sort(pivotFinalIndex + 1, right, arr);
    }

    /**
     * Partition a section of an array around a pivot value
     * @param left  Lower-bound index of section (inclusive)
     * @param right Upper-bound index of section (inclusive)
     * @param pivot Index of the value to partition around
     * @param arr   Array to perform partitioning within
     * @param <E>   Type of the elements contained by arr
     * @return      The final index of the partition value
     */
    private static <E extends Comparable> int partition(int left, int right, int pivot, ArrayList<E> arr) {
        // Move pivot to left-most position (get out of the way)
        Collections.swap(arr, left, pivot);
        pivot = left;

        // Perform partitioning
        int rightPartitionStart = left + 1;
        for (int i = left + 1; i <= right; i++) {
            // If our current value is less than our pivot, move it into the left partition
            if (arr.get(i).compareTo(arr.get(pivot)) < 0) {
                Collections.swap(arr, i, rightPartitionStart);
                rightPartitionStart++;
            }
        }

        // Put pivot back where it belongs (in between partitions)
        Collections.swap(arr, pivot, rightPartitionStart - 1);
        pivot = rightPartitionStart - 1;

        return pivot;
    }
}

Answer 1

1

I would declare <E extends Comparable> void sort(ArrayList<E> arr) as <E extends Comparable<? super E>> void sort(ArrayList<E> arr)

2

void sort(int left, int right, ArrayList<E> arr) {
    ...
}

I suggest you make it public and reorganize the arguments like this:

void sort(ArrayList<E> arr, int fromIndex, int toIndex)

where fromIndex corresponds to left in your version, and toIndex corresponds to right + 1: these are the conventions in JDK's sort algorithms, so that toIndex is an exclusive upper bound.

3

I would make the three-parameter version public since sometimes people want to sort only a subrange of an array (or ArrayList in our case).

4

Declare the constructor as private:

private Quicksort() {}

Hope that helps.