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

User · Answer

How about using streams  Java 8    int   ia    99  11  7  21  4  2   ia   Arrays stream ia       boxed        sorted  a  b  - gt  b compareTo a       sort descending     mapToInt i - gt  i       toArray      Or in-place   int   ia    99  11  7  21  4  2   System arraycopy          Arrays stream ia               boxed                sorted  a  b  - gt  b compareTo a       sort descending             mapToInt i - gt  i               toArray            0          ia          0          ia length

User · Answer

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  lt  data length   0  i             for int j   i  j  gt  0              amp  amp  comparator compare data j - 1   data j    gt  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  amp  amp   onlyNinesB               return -1                    if onlyNinesB  amp  amp   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  lt  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

User · Answer

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 lt Integer gt  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 lt Integer gt          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

User · Answer

If you don t want to copy the array  say it is very large   you might want to create a wrapper List lt Integer gt  that can be used in a sort   final int   elements    1  2  3  4   List lt Integer gt  wrapper   new AbstractList lt Integer gt                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

User · Answer

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  lt   right  i                     int temp   arr i            int j   i - 1           while  j  gt   left  amp  amp  comparator compare arr j   temp   gt  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  lt  len1  x                     left x    arr l   x               for  int x   0  x  lt  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  lt  len1  amp  amp  j  lt  len2                   if  comparator compare left i   right j    lt   0                         arr k    left i                i                        else                         arr k    right j                j                        k                    copy remaining elements of left  if any       while  i  lt  len1                  arr k    left i            k             i                    copy remaining element of right  if any       while  j  lt  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  lt  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  lt  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  lt  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   amp                   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

User · Answer

By transforming your int array into an Integer one and then using public static  lt T gt  void Arrays sort T   a   Comparator lt   super T gt  c   the first step is only needed as I fear autoboxing may bot work on arrays

User · Answer

java 8  Arrays stream new int   10 4 5 6 1 2 3 7 9 8   boxed   sorted  e1 e2 - gt  e2-e1  collect Collectors toList

User · Answer

You don t need external library   Integer   input   Arrays stream arr  boxed   toArray Integer    new   Arrays sort input   a  b  - gt  b - a      reverse order return Arrays stream input  mapToInt Integer  intValue  toArray

User · Answer

You can use IntArrays quickSort array  comparator  from fastutil library

User · Answer

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 lt Integer gt          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

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

Examples related to java

Examples related to sorting