Search code examples
javaeclipse-collections

Eclipse Collections sorting an IntList by a custom comparator-like function without boxing


I'm trying to sort a few (Mutable)IntList objects. The cost of boxing/unboxing integers is relevant in my program (which is exactly why I am using the primitive collections). I want to sort by the following criteria:

  • All negative numbers come before non-negative numbers
  • Smallest (closest to zero) numbers first

[1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]

Is there a sorting method for the IntList class in the Eclipse Collections library that allow a custom comparator? So far I have not found it, but the list of defined symbols is large, the search box only matches exact strings and documentation is hardly existent (mostly automatically generated from method signatures, I believe).

My last resort is to write my own int-int comparator and sorting function, which is not a big deal, but I'd rather not.

Please do not waste your time writing a proof of concept sorter, as much as I'd appreciate it.. I know how to sort a list, I just can't figure out how to locate stuff in the Eclipse Collections documentation. If you can help with that, feel free to include it in your answer.


Solution

  • Since there was no 'quick' answer here either, I went ahead and implemented such a sorting device myself.

    public class IntListUtils {
        public interface IntIntComparator {
            int compare(int a, int b);
        }
    
        public static void sort(MutableIntList subject, IntIntComparator comparator) {
            quicksort(subject, 0, subject.size() - 1, comparator);
        }
    
        public static void quicksort(MutableIntList subject, int low, int high, IntIntComparator comparator) {
            if (low >= high) { return; }
            int pivot = partition(subject, low, high, comparator);
            quicksort(subject, low, pivot - 1, comparator);
            quicksort(subject, pivot, high, comparator);
        }
    
        private static int partition(MutableIntList subject, int low, int high, IntIntComparator comparator) {
            int pivot = subject.get(high);
            int i = low;
            for (int j = low; j <= high - 1; j++) {
                if (comparator.compare(subject.get(j), pivot) < 0) {
                    int t = subject.get(i);
                    subject.set(i, subject.get(j));
                    subject.set(j, t);
                    i += 1;
                }
            }
            int t = subject.get(i);
            subject.set(i, subject.get(high));
            subject.set(high, t);
            return i;
        }
    }
    

    Which can be used as such to achieve the sorting order as I described above:

    MutableIntList list = ...;
    IntListUtils.sort(list, (a, b) -> {
        // negative before non-negative
        // otherwise, smallest numbers first
        if (a == b) { return 0; }
        if (a < 0 && b < 0) {
            return (a < b) ? 1 : -1;
        }
        return (a < b) ? -1 : 1;
    });
    

    EDIT: I realize this quicksort is not the fastest sort method out there, but all it has to do is be faster than converting my entire IntList into a List<Integer> and back after sorting, which allocates O(n) memory (n is large) while this sorting method happens in-place.