5
\$\begingroup\$

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;
    }
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Cool, thanks for the great suggestions! The only one I'm not sure of the reasoning for is the first point. I get that it's basically saying that E must extend a Comparable that is of a type which is also a parent/ancestor of E. But what exactly does that gain me? As long as E is Comparable, everything should work as expected, right? \$\endgroup\$ – PseudoPsyche Mar 27 '16 at 14:26
  • \$\begingroup\$ I am not sure, but it might be that the same byte code is generated. You can verify this by using the javap program for disassembling your class files. \$\endgroup\$ – coderodde Apr 8 '16 at 14:57
  • \$\begingroup\$ Gotcha. Would you consider this to be "best (or at least better) practice", since it is technically being more explicit? (regardless of whether the generated bytecode is the same or not) I'm just asking because I've honestly never run into it before. \$\endgroup\$ – PseudoPsyche Apr 8 '16 at 15:01
  • \$\begingroup\$ docs.oracle.com/javase/8/docs/api/java/util/… JDK relies on that more explicit <? super T> - signature. \$\endgroup\$ – coderodde Apr 8 '16 at 15:06
  • \$\begingroup\$ Actually, this is a good question. The fact that we have choice within this issue, may be caused by historic rather than technical reasons, and I suspect it to be compatibility towards pre-Java 5 code, which has had no generics available. Go figure. \$\endgroup\$ – coderodde Apr 8 '16 at 15:17

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.