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

Question

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.

score 3 · Answer 1 · answered Mar 28 '21 at 17:57

Indirect sort support for primitive collections was introduced in Eclipse Collections starting with version 10.3. It is supported on mutable primitive collections. You can see more details and usage examples at https://medium.com/javarevisited/eclipse-collections-now-supports-indirect-sorting-of-primitive-lists-e2447ca5dbc3

The OP example would look like this:

@Test
public void soTest()
{
    // [1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]
    MutableIntList list = IntLists.mutable.of(1, 7, 0, -9, -3);

    list.sortThis((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;}
    );

    Assert.assertEquals(IntLists.immutable.of(-3, -9, 0, 1, 7), list);
}

The comparator lambda may be simplified to:

list.sortThis((a, b) ->
        (a < 0 && b < 0) ? Integer.compare(b, a) : Integer.compare(a, b));

score 1 · Answer 2 · answered Oct 04 '18 at 14:08

1

IntList is the interface which MutableIntList and ImmutableIntList extended.

I'm seeing there is an implementation class which may help you in this case is IntArrayList which is implementation of MutableIntList.

There is a sortThis() method which is performing

Arrays.sort(this.items, 0, this.size);

So for you example it will return -9, -3, 0, 1, 7

But I noticed you would like to have -3, -9, 0, 1, 7. I'm not sure this is a typo or this is a requirement. When you check it, we can discuss further

answered Oct 04 '18 at 14:08

Nghia Do

2,588
2
17
31

This is not a typo, this is the exact reason I want a sort method that takes a comparator. – Jochem Kuijpers Oct 04 '18 at 14:10
If so I would you create a class extends IntArrayList and override sortThis() methods – Nghia Do Oct 04 '18 at 17:00
Since IntArrayLists is (as far as I'm aware) the only standard implementation, this would be fine. I currently use a static method in a utility class, though. – Jochem Kuijpers Oct 06 '18 at 10:26

Jochem Kuijpers · Accepted Answer · 2018-10-04T14:45:26.680

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.

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

3 Answers3