How to sort an array of ints using a custom comparator?

Question

I need to sort an array of ints using a custom comparator, but Java's library doesn't provide a sort function for ints with comparators (comparators can be used only with objects). Is there any easy way to do this?

Answer 1

I had the same requirement of sorting a primitive int array in descending order. After going through the solutions here, I came up with the below two solutions, which achieve the same outcome.

Version 1:

Using ArrayUtils class functions. It requires adding commons-lang external library (or importing org.apache.commons.lang package).

private int[] sortDescending(int[] source) {
    Integer[] intObjArr = ArrayUtils.toObject(source);
    Arrays.sort(intObjArr, Comparator.reverseOrder());

    return ArrayUtils.toPrimitive(intObjArr);
}

Version 2:

Using Arrays.stream() and available functions to box the int values, sort and, map them back to primitive type array.

private int[] sortDescending(int[] source) {
    return Arrays.stream(source)
            .boxed()
            .sorted(Comparator.reverseOrder())
            .mapToInt(num -> num)
            .toArray();
}

Instead of Comparator.reverseOrder(), we can also use the following.

Implementation of compareTo() method provided by Integer class.

(e1, e2) -> e2.compareTo(e1);

Manually implementing a sorting algorithm.

private int[] sortDescending(int[] source) {
       return Arrays.stream(source)
               .boxed()
               .sorted((e1, e2) -> {
                   /* This casting to long is to prevent Integer Overflow/Underflow issue. */
                   long diff = (long) e2 - (long) e1;
                   if (diff < 0) {
                       return -1;
                   } else if (diff > 0) {
                       return 1;
                   }
                   return 0;
               })
               .mapToInt(num -> num)
               .toArray();    
}

Thank you so much for this question and the prior answers.

Answer 2

If you are interested with performance and reducing number of object created on the way consider using implementation from eclipse collections.

It uses custom IntComparator, which operates on primitives thus no boxing is required.

Answer 3

java 8:

Arrays.stream(new int[]{10,4,5,6,1,2,3,7,9,8}).boxed().sorted((e1,e2)-> e2-e1).collect(Collectors.toList());

Answer 4

Here is some code (it's actually not Timsort as I originally thought, but it does work well) that does the trick without any boxing/unboxing. In my tests, it works 3-4 times faster than using Collections.sort with a List wrapper around the array.

// This code has been contributed by 29AjayKumar 
// from: https://www.geeksforgeeks.org/sort/

static final int sortIntArrayWithComparator_RUN = 32; 

// this function sorts array from left index to  
// to right index which is of size atmost RUN  
static void sortIntArrayWithComparator_insertionSort(int[] arr, IntComparator comparator, int left, int right) { 
    for (int i = left + 1; i <= right; i++)  
    { 
        int temp = arr[i]; 
        int j = i - 1; 
        while (j >= left && comparator.compare(arr[j], temp) > 0)
        { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = temp; 
    } 
} 

// merge function merges the sorted runs  
static void sortIntArrayWithComparator_merge(int[] arr, IntComparator comparator, int l, int m, int r) { 
    // original array is broken in two parts  
    // left and right array  
    int len1 = m - l + 1, len2 = r - m; 
    int[] left = new int[len1]; 
    int[] right = new int[len2]; 
    for (int x = 0; x < len1; x++)  
    { 
        left[x] = arr[l + x]; 
    } 
    for (int x = 0; x < len2; x++)  
    { 
        right[x] = arr[m + 1 + x]; 
    } 

    int i = 0; 
    int j = 0; 
    int k = l; 

    // after comparing, we merge those two array  
    // in larger sub array  
    while (i < len1 && j < len2)  
    { 
        if (comparator.compare(left[i], right[j]) <= 0)
        { 
            arr[k] = left[i]; 
            i++; 
        } 
        else 
        { 
            arr[k] = right[j]; 
            j++; 
        } 
        k++; 
    } 

    // copy remaining elements of left, if any  
    while (i < len1) 
    { 
        arr[k] = left[i]; 
        k++; 
        i++; 
    } 

    // copy remaining element of right, if any  
    while (j < len2)  
    { 
        arr[k] = right[j]; 
        k++; 
        j++; 
    } 
} 

// iterative sort function to sort the  
// array[0...n-1] (similar to merge sort)  
static void sortIntArrayWithComparator(int[] arr, IntComparator comparator) { sortIntArrayWithComparator(arr, lIntArray(arr), comparator); }
static void sortIntArrayWithComparator(int[] arr, int n, IntComparator comparator) { 
    // Sort individual subarrays of size RUN  
    for (int i = 0; i < n; i += sortIntArrayWithComparator_RUN)  
    { 
        sortIntArrayWithComparator_insertionSort(arr, comparator, i, Math.min((i + 31), (n - 1))); 
    } 

    // start merging from size RUN (or 32). It will merge  
    // to form size 64, then 128, 256 and so on ....  
    for (int size = sortIntArrayWithComparator_RUN; size < n; size = 2 * size)  
    { 
          
        // pick starting point of left sub array. We  
        // are going to merge arr[left..left+size-1]  
        // and arr[left+size, left+2*size-1]  
        // After every merge, we increase left by 2*size  
        for (int left = 0; left < n; left += 2 * size)  
        { 
              
            // find ending point of left sub array  
            // mid+1 is starting point of right sub array  
            int mid = Math.min(left + size - 1, n - 1);
            int right = Math.min(left + 2 * size - 1, n - 1); 

            // merge sub array arr[left.....mid] &  
            // arr[mid+1....right]  
            sortIntArrayWithComparator_merge(arr, comparator, left, mid, right); 
        } 
    } 
}

static int lIntArray(int[] a) {
  return a == null ? 0 : a.length;
}

static interface IntComparator {
  int compare(int a, int b);
}

Answer 5

You don't need external library:

Integer[] input = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(input, (a, b) -> b - a); // reverse order
return Arrays.stream(input).mapToInt(Integer::intValue).toArray();

Answer 6

If you don't want to copy the array (say it is very large), you might want to create a wrapper List<Integer> that can be used in a sort:

final int[] elements = {1, 2, 3, 4};
List<Integer> wrapper = new AbstractList<Integer>() {

        @Override
        public Integer get(int index) {
            return elements[index];
        }

        @Override
        public int size() {
            return elements.length;
        }

        @Override
        public Integer set(int index, Integer element) {
            int v = elements[index];
            elements[index] = element;
            return v;
        }

    };

And now you can do a sort on this wrapper List using a custom comparator.

Answer 7

You can use IntArrays.quickSort(array, comparator) from fastutil library.

Answer 8

If you can't change the type of your input array the following will work:

final int[] data = new int[] { 5, 4, 2, 1, 3 };
final Integer[] sorted = ArrayUtils.toObject(data);
Arrays.sort(sorted, new Comparator<Integer>() {
    public int compare(Integer o1, Integer o2) {
        // Intentional: Reverse order for this demo
        return o2.compareTo(o1);
    }
});
System.arraycopy(ArrayUtils.toPrimitive(sorted), 0, data, 0, sorted.length);

This uses ArrayUtils from the commons-lang project to easily convert between int[] and Integer[], creates a copy of the array, does the sort, and then copies the sorted data over the original.

Answer 9

How about using streams (Java 8)?

int[] ia = {99, 11, 7, 21, 4, 2};
ia = Arrays.stream(ia).
    boxed().
    sorted((a, b) -> b.compareTo(a)). // sort descending
    mapToInt(i -> i).
    toArray();

Or in-place:

int[] ia = {99, 11, 7, 21, 4, 2};
System.arraycopy(
        Arrays.stream(ia).
            boxed().
            sorted((a, b) -> b.compareTo(a)). // sort descending
            mapToInt(i -> i).
            toArray(),
        0,
        ia,
        0,
        ia.length
    );

Answer 10

I tried maximum to use the comparator with primitive type itself. At-last i concluded that there is no way to cheat the comparator.This is my implementation.

public class ArrSortComptr {
    public static void main(String[] args) {

         int[] array = { 3, 2, 1, 5, 8, 6 };
         int[] sortedArr=SortPrimitiveInt(new intComp(),array);
         System.out.println("InPut "+ Arrays.toString(array));
         System.out.println("OutPut "+ Arrays.toString(sortedArr));

    }
 static int[] SortPrimitiveInt(Comparator<Integer> com,int ... arr)
 {
    Integer[] objInt=intToObject(arr);
    Arrays.sort(objInt,com);
    return intObjToPrimitive(objInt);

 }
 static Integer[] intToObject(int ... arr)
 {
    Integer[] a=new Integer[arr.length];
    int cnt=0;
    for(int val:arr)
      a[cnt++]=new Integer(val);
    return a;
 }
 static int[] intObjToPrimitive(Integer ... arr)
 {
     int[] a=new int[arr.length];
     int cnt=0;
     for(Integer val:arr)
         if(val!=null)
             a[cnt++]=val.intValue();
     return a;

 }

}
class intComp implements Comparator<Integer>
{

    @Override //your comparator implementation.
    public int compare(Integer o1, Integer o2) {
        // TODO Auto-generated method stub
        return o1.compareTo(o2);
    }

}

@Roman: I can't say that this is a good example but since you asked this is what came to my mind. Suppose in an array you want to sort number's just based on their absolute value.

Integer d1=Math.abs(o1);
Integer d2=Math.abs(o2);
return d1.compareTo(d2);

Another example can be like you want to sort only numbers greater than 100.It actually depends on the situation.I can't think of any more situations.Maybe Alexandru can give more examples since he say's he want's to use a comparator for int array.

Answer 11

Here is a helper method to do the job.

First of all you'll need a new Comparator interface, as Comparator doesn't support primitives:

public interface IntComparator{
    public int compare(int a, int b);
}

(You could of course do it with autoboxing / unboxing but I won't go there, that's ugly)

Then, here's a helper method to sort an int array using this comparator:

public static void sort(final int[] data, final IntComparator comparator){
    for(int i = 0; i < data.length + 0; i++){
        for(int j = i; j > 0
            && comparator.compare(data[j - 1], data[j]) > 0; j--){
            final int b = j - 1;
            final int t = data[j];
            data[j] = data[b];
            data[b] = t;
        }
    }
}

And here is some client code. A stupid comparator that sorts all numbers that consist only of the digit '9' to the front (again sorted by size) and then the rest (for whatever good that is):

final int[] data =
    { 4343, 544, 433, 99, 44934343, 9999, 32, 999, 9, 292, 65 };
sort(data, new IntComparator(){

    @Override
    public int compare(final int a, final int b){
        final boolean onlyNinesA = this.onlyNines(a);
        final boolean onlyNinesB = this.onlyNines(b);
        if(onlyNinesA && !onlyNinesB){
            return -1;
        }
        if(onlyNinesB && !onlyNinesA){
            return 1;
        }

        return Integer.valueOf(a).compareTo(Integer.valueOf(b));
    }

    private boolean onlyNines(final int candidate){
        final String str = String.valueOf(candidate);
        boolean nines = true;
        for(int i = 0; i < str.length(); i++){
            if(!(str.charAt(i) == '9')){
                nines = false;
                break;
            }
        }
        return nines;
    }
});

System.out.println(Arrays.toString(data));

Output:

[9, 99, 999, 9999, 32, 65, 292, 433, 544, 4343, 44934343]

The sort code was taken from Arrays.sort(int[]), and I only used the version that is optimized for tiny arrays. For a real implementation you'd probably want to look at the source code of the internal method sort1(int[], offset, length) in the Arrays class.

Answer 12

By transforming your int array into an Integer one and then using public static <T> void Arrays.sort(T[] a, Comparator<? super T> c) (the first step is only needed as I fear autoboxing may bot work on arrays).