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:
[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.
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.