Arrays.sort() en Java avec des exemples

Java

Arrays.sort() en Java avec des exemples | Dans cet article, nous verrons comment trier un tableau à l'aide de Arrays.sort() en Java ? Quel est le moyen efficace de trier les tableaux Java ? Comment utiliser la méthode Arrays.sort() en Java ? Comment utiliser Arrays.parallelSort() en Java ? Quelles sont les différences entre la méthode Java Arrays.sort() et Arrays.parallelSort() ?

Il existe de nombreux algorithmes de tri disponibles pour résoudre un seul problème, c'est-à-dire trier un tableau. Ils ont une complexité temporelle et une complexité spatiale différentes. Mais parmi tous les algorithmes de tri, Quick Sort donne les meilleures performances.

La complexité temporelle de Quicksort est O(n log n) dans le meilleur des cas, O(n log n) dans le cas moyen, et O(n^2) dans le pire des cas. Mais comme il offre les meilleures performances dans le cas moyen pour la plupart des entrées, Quicksort est généralement considéré comme l'algorithme de tri "le plus rapide".

Dans la classe java.util.Arrays, plusieurs méthodes sort() sont disponibles. Tous utilisent Quicksort à double pivot. Le Tri rapide à double pivot est donné par Vladimir Yaroslavskiy, Jon Bentley et Josh Bloch. Cet algorithme offre des performances O(n log(n)) sur tous les ensembles de données et est généralement plus rapide que les implémentations Quicksort traditionnelles (à un pivot).

Le tri rapide à double pivot est un peu plus rapide que le tri rapide à pivot unique d'origine. Mais encore, le pire des cas restera O(n^2) lorsque le tableau est déjà trié dans un ordre croissant ou décroissant.

Remarque :- Lorsque vous travaillez avec des tableaux Java, vous n'avez pas besoin d'écrire votre propre logique pour implémenter un algorithme de tri. Importez simplement la classe Arrays et utilisez Arrays.sort() en Java qui offre les meilleures performances dans la plupart des cas par rapport aux autres algorithmes de tri.

Dans la classe Arrays, plusieurs méthodes sort() surchargées sont disponibles. Ce sont,

public static void sort(byte[] a)
public static void sort(short[] a)
public static void sort(int[] a)
public static void sort(long[] a)
public static void sort(float[] a)
public static void sort(double[] a)
public static void sort(char[] a)
public static void sort(Object[] a)
public static void sort(byte[] a, int fromIndex, int toIndex)
public static void sort(short[] a, int fromIndex, int toIndex)
public static void sort(int[] a, int fromIndex, int toIndex)
public static void sort(long[] a, int fromIndex, int toIndex)
public static void sort(float[] a, int fromIndex, int toIndex)
public static void sort(double[] a, int fromIndex, int toIndex)
public static void sort(char[] a, int fromIndex, int toIndex)
public static void sort(Object[] a, int fromIndex, int toIndex)

Tableaux.sort(tableau) :- Il trie le tableau complet par ordre croissant.
Arrays.sort(array, fromIndex, toIndex) :- Il trie uniquement les éléments de fromIndex à toIndex.

Programmer pour trier un tableau en utilisant Arrays.sort() en Java

Montrons un exemple de tri d'un tableau à l'aide de Arrays.sort() en Java.

import java.util.Arrays;

public class SortArray {
  
  // main method
  public static void main(String[] args) {

    // declare and initialize arrays
    int arr[] = {50, 25, 30, 55, 15};
    
    // display array before sorting
    System.out.println("Before Sorting: " + Arrays.toString(arr));
    
    // sort array
    Arrays.sort(arr);
    
    // display array after sorting
    System.out.println("After Sorting: " + Arrays.toString(arr));
  }
}

Sortie :-

Avant tri :[50, 25, 30, 55, 15]
Après tri :[15, 25, 30, 50, 55]

Maintenant, démontrons le tableau byte, short, long, float, double, char, boolean.

Trier un tableau d'octets à l'aide de Arrays.sort() en Java,

// byte array
byte[] byteArr = {15, 12, 11, 14, 13};
Arrays.sort(byteArr);
System.out.println("Byte Array = " + Arrays.toString(byteArr));

Tableau d'octets =[11, 12, 13, 14, 15]

Trier un tableau de shorts à l'aide de Arrays.sort() en Java,

// short array
short[] shortArr = {400, 200, 100, 300, 500};
Arrays.sort(shortArr);
System.out.println("Short Array = " + Arrays.toString(shortArr));

Tableau court =[100, 200, 300, 400, 500]

Trier le tableau de longs en utilisant Arrays.sort() en Java,

// long array
long[] longArr = {999999999, 10, 500, -888888888, 0};
Arrays.sort(longArr);
System.out.println("Long Array = " + Arrays.toString(longArr));

Tableau long =[-888888888, 0, 10, 500, 999999999]

Trier un tableau de flottants à l'aide de Arrays.sort() en Java,

// float array
float[] floatArr = {15.9f, 10.5f, 500, -88888, 0.9f};
Arrays.sort(floatArr);
System.out.println("Float Array = " + Arrays.toString(floatArr));

Tableau flottant =[-88888.0, 0.9, 10.5, 15.9, 500.0]

Trier un tableau de doubles à l'aide de Arrays.sort() en Java,

// double array
double[] doubleArr = {10.5, 15.9, 500, -88888, 0.9};
Arrays.sort(doubleArr);
System.out.println("Double Array = " + Arrays.toString(doubleArr));

Double tableau =[-88888.0, 0.9, 10.5, 15.9, 500.0]

Trier un tableau de caractères à l'aide de Arrays.sort() en Java,

// char array
char[] charArr = {'K','n','o','w','P','r','o','g','r',97,'m'};
Arrays.sort(charArr);
System.out.println("Char Array = " + Arrays.toString(charArr));

Tableau de caractères =[K, P, a, g, m, n, o, o, r, r, w]

L'opération de tri n'est pas applicable aux valeurs booléennes. La valeur booléenne peut contenir true ou false. Par conséquent, la classe Arrays ne contient aucune méthode pour trier le tableau booléen. Le code ci-dessous donne une erreur.

// boolean array
boolean[] boolArr = {true, false, true, true, false};
Arrays.sort(boolArr); // error

Si le tableau spécifié est référencé à null, alors Arrays.sort() en Java ne donne aucune erreur ou exception.

int arr[] = null;
Arrays.sort(arr); // valid

Exemple de tri avec Arrays.sort(array, fromIndex, toIndex)

En utilisant Arrays.sort(array, fromIndex, toIndex) en Java, nous ne pouvons trier que les éléments d'une plage particulière. Ici depuisIndex est l'indice du premier élément , inclusif , à trier et àIndex est l'indice du dernier élément , exclusif , à trier.

de l'index :- index du premier élément, inclus.
toIndex :- index du dernier élément, exclusif.

import java.util.Arrays;

public class SortArray {
  
  // main method
  public static void main(String[] args) {

    // declare and initialize arrays
    int arr[] = {50, 25, 30, 55, 15};
    
    // display array before sorting
    System.out.println("Before Sorting: " + Arrays.toString(arr));
    
    // sort array
    Arrays.sort(arr, 0, 3);
    
    // display array after sorting
    System.out.println("After Sorting: " + Arrays.toString(arr));
  }
}

Sortie :-

Avant tri :[50, 25, 30, 55, 15]
Après tri :[25, 30, 50, 55, 15]

Voyons quelques exemples supplémentaires avec Arrays.sort(array, fromIndex, toIndex)

// char array
char[] charArr1 = {'k','n','o','w','p','r','o','g','r','a','m'};
// sort only {'p','r','o','g','r',97,'m'}
Arrays.sort(charArr1, 4, charArr1.length);
System.out.println("Char Array = " + Arrays.toString(charArr1));

Tableau de caractères =[k, n, o, w, a, g, m, o, p, r, r]

// char array
char[] charArr2 = {'k','n','o','w','p','r','o','g','r','a','m'};
// sort only {'n','o','w,,'p','r','o'}
Arrays.sort(charArr2, 1, 7);
System.out.println("Char Array = " + Arrays.toString(charArr2));

Tableau de caractères =[k, n, o, o, p, r, w, g, r, a, m]

Exceptions levées par Arrays.sort(array, fromIndex, toIndex) en Java

IllegalArgumentException :- si depuisIndex> versIndex
Exception ArrayIndexOutOfBounds :- si fromIndex <0 ou toIndex> a.length

int arr[] = {50, 25, 30, 55, 15};
Arrays.sort(arr, 5, 0);

Exception dans le thread "principal" java.lang.IllegalArgumentException :fromIndex(5)> toIndex(0)

int arr[] = {50, 25, 30, 55, 15};
Arrays.sort(arr, -9, 5);

Exception dans le thread "principal" java.lang.ArrayIndexOutOfBoundsException :index de tableau hors plage :-9

int arr[] = {50, 25, 30, 55, 15};
Arrays.sort(arr, 0, 7);

Exception dans le thread "principal" java.lang.ArrayIndexOutOfBoundsException :index de tableau hors plage :7

Arrays.parallelSort() en Java

La classe java.util.Arrays contient également la méthode parallelSort() pour trier un tableau. Il trie également le tableau spécifié dans l'ordre numérique croissant. Il est ajouté en Java8.

Similitude avec Arrays.parallelSort() et Arrays.sort() en Java

Les deux peuvent être utilisés pour trier des objets et des tableaux primitifs.
Par défaut, les deux méthodes trient un tableau par ordre croissant.

Contrairement à Arrays.sort() en Java (qui est basé sur un seul thread), il utilise plusieurs threads. Et pour exécuter des tâches parallèles, il utilise le pool ForkJoin. Il utilise une technique de tri-fusion qui divise le tableau spécifié en morceaux d'une certaine taille et trie chaque morceau individuellement. Enfin, les morceaux triés sont fusionnés à l'aide de la logique de fusion de l'algorithme Merge-sort.

L'implémentation dans JDK 8 utilise cette approche :-
1) Divisez le tableau en 4 parties.
2) Triez les deux premières parties, puis fusionnez-les.
3) Triez les deux parties suivantes puis fusionnez-les.

Les étapes ci-dessus sont répétées de manière récursive avec chaque pièce jusqu'à ce que la taille de la pièce à trier ne soit pas inférieure à la valeur seuil calculée ci-dessus.

Remarque :- Arrays.parallelSort() en Java utilise le parallélisme uniquement lorsque certaines conditions sont remplies. Si la taille du tableau est inférieure ou égale à 8192 ou si le processeur n'a qu'un seul cœur, il utilise en interne la méthode Arrays.sort().

Semblable à Arrays.sort() en Java, il a également deux variantes pour trier un tableau complet et un tableau partiel,

Tableaux.parallelSort(tableau) :- Il trie le tableau complet par ordre croissant.
Arrays.parallelSort(array, fromIndex, toIndex) :- Il trie uniquement les éléments de fromIndex à toIndex.

import java.util.Arrays;

public class CompareArray {
  
  // main method
  public static void main(String[] args) {

    // declare and initialize arrays
    int arr[] = {50, 30, 25, 55, 15};
    
    // sort array
    Arrays.parallelSort(arr);
    
    // display array after sorting
    System.out.println(Arrays.toString(arr));
  }
}

Sortie :-

[15, 25, 30, 50, 55]

Un autre exemple consiste à trier le tableau uniquement les éléments particuliers de fromIndex à toIndex,

// declare and initialize arrays
int arr[] = {50, 30, 25, 55, 15};
    
// sort array using parallelSort()
Arrays.parallelSort(arr, 1, 3);
    
// display array after sorting
System.out.println(Arrays.toString(arr));

Sortie :-

[50, 25, 30, 55, 15]

Arrays.sort() en Java et Arrays.parallelSort()

Tableaux.sort()	Arrays.parallelSort()
Pour effectuer l'opération, il utilise un seul thread. Par conséquent, le tri est effectué de manière séquentielle, c'est-à-dire que l'ensemble du tableau est trié à l'aide d'un seul thread.	Pour effectuer l'opération, il utilise plusieurs threads. Le tri se fait en parallèle. c'est-à-dire que plusieurs threads s'exécutent en parallèle pour trier le morceau du tableau.
Il est plus rapide pour les petites tailles de tableaux, mais donne moins de performances pour les grands ensembles de données et prend un peu plus de temps pour effectuer l'opération.	Il est plus lent pour les petits ensembles de données mais offre de meilleures performances pour les tableaux de grande taille.
Il n'utilise pas les multiples cœurs du système.	Il utilise les multiples cœurs du système.