Let quicksort support empty lists

[webmaster128]

I just tried to sort an empty list, using Quicksort when I got this exception

aused by: java.lang.IllegalArgumentException: Argument 1 must be greater than or equal to Argument 2. Argument 1: -1 Argument 2: 0
            at net.kullo.android.external.ExceptionUtility.verifyGreaterThanOrEqual(ExceptionUtility.java:118)
            at me.external.Quicksort$GenericList.quicksort(Quicksort.java:366)
            at me.external.Quicksort$GenericList.quicksort(Quicksort.java:360)

The exception makes sense when the input list is empty, because in this case, the following code tries to sort from 0 to -1.

        public static <T> void quicksort(List<T> array, Comparator<T> comparator) {
            quicksort(array, 0, array.size() - 1, comparator);
        }

Question: Would you like that to be fixed in the implementation (I'd create a PR) or do you think it is the application's job to do the case distinction?

I never had the problem with Java's Collections.sort().

[webmaster128]

Okay I just discovered that the algorithm is fundamentally broken.

[michiexile]

A pull request would be welcome.

[webmaster128]

I implemented Quicksort myself after finding that this one does not work: https://github.com/kullo/javautils/tree/master/src/main/java/net/kullo/javautils

Feel to either use this one or reuse the code (Apache license). There you can find tests as well.

[melvyniandrag]

Hi,
I've been playing around with this software for a few months - thanks for writing this, it has made it possible for me to experiment with persistent homology!

I thought that working on this sorting problem would be an easy way for me to make a teensy contribution to the project. I just checked to see where and when Quicksort is called and it looks like it isn't even used! Am I forgetting to look somewhere?

This doesn't seem to be imported or called anywhere except in Quicksort.java. If that's the case then this issue is a nonissue and could be closed, right?

$ grep -r "Quicksort" .
Binary file ./.git/index matches
Binary file ./.git/objects/pack/pack-6ccb7187f3c99ac6bc66743a0c101f85195c8236.pack matches
Binary file ./src/matlab/for_distribution/lib/javaplex.jar matches
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:public class Quicksort {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:      private Quicksort() {}
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:              public static void randomizedQuicksort(int[] array) {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:              public static void randomizedQuicksort(int[] array, int startIndex, int endIndex) {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:                              randomizedQuicksort(array, startIndex, partitionBoundaryIndex);
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:                              randomizedQuicksort(array, partitionBoundaryIndex + 1, endIndex);
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:              public static <T> void randomizedQuicksort(T[] array, Comparator<T> comparator) {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:              public static <T> void randomizedQuicksort(T[] array, int startIndex, int endIndex, Comparator<T> comparator) {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:                              randomizedQuicksort(array, startIndex, partitionBoundaryIndex, comparator);
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:                              randomizedQuicksort(array, partitionBoundaryIndex + 1, endIndex, comparator);
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:              public static <T> void randomizedQuicksort(List<T> array, Comparator<T> comparator) {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:              public static <T> void randomizedQuicksort(List<T> array, int startIndex, int endIndex, Comparator<T> comparator) {
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:                              randomizedQuicksort(array, startIndex, partitionBoundaryIndex, comparator);
./src/java/edu/stanford/math/plex4/utility/Quicksort.java:                              randomizedQuicksort(array, partitionBoundaryIndex + 1, endIndex, comparator);

[michiexile]

Closing according to @melvyniandrag 's check.

[webmaster128]

I think the broken unused file Quicksort.java should be removed than to avoid additional confusion.