Comment trier un tableau d'entiers en utilisant un comparateur personnalisé ?

Question

J'ai besoin de trier un tableau d'entiers en utilisant un comparateur personnalisé, mais la bibliothèque Java ne fournit pas de fonction de tri pour les entiers avec des comparateurs (les comparateurs ne peuvent être utilisés qu'avec des objets). Existe-t-il un moyen simple de le faire ?

Answer 1

En transformant votre tableau d'int en un tableau d'Integer et en utilisant ensuite public static <T> void Arrays.sort(T[] a, Comparator<? super T> c) (la première étape n'est nécessaire que parce que je crains que l'autoboxing ne fonctionne pas sur les tableaux).

Answer 2

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 3

Si vous êtes intéressé par la performance et la réduction du nombre d'objets créés en cours de route, envisagez d'utiliser l'implémentation de les collections d'éclipse .

Il utilise des IntComparator qui opère sur des primitives et ne nécessite donc aucune mise en boîte.

Answer 4

Voici un code (ce n'est en fait pas Timsort comme je le pensais au départ, mais il fonctionne bien) qui fait l'affaire sans aucun boxing/unboxing. Dans mes tests, cela fonctionne 3 à 4 fois plus vite qu'en utilisant Collections.sort avec un wrapper List autour du tableau.

// 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

Voici une méthode d'aide pour faire le travail.

Tout d'abord, vous aurez besoin d'une nouvelle interface Comparator, comme suit Comparateur ne prend pas en charge les primitives :

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

(Vous pourriez bien sûr le faire avec l'autoboxing / unboxing mais je ne m'aventurerai pas sur ce terrain, c'est moche).

Ensuite, voici une méthode d'aide pour trier un tableau d'int en utilisant ce comparateur :

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;
        }
    }
}

Et voici un peu de code client. Un comparateur stupide qui trie tous les nombres qui ne sont constitués que du chiffre '9' au début (encore une fois triés par taille) et ensuite le reste (pour n'importe quelle raison) :

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));

Sortie :

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

Le code de tri a été repris de Arrays.sort(int[]) et je n'ai utilisé que la version optimisée pour les petits tableaux. Pour une implémentation réelle, vous voudrez probablement regarder le code source de la méthode interne sort1(int[], offset, length) en el Tableaux classe.