Introduction au tri en Java
- Le tri en Java consiste essentiellement à organiser un groupe d'éléments stockés quelque part dans un ordre particulier, cet ordre peut être à la fois croissant ou décroissant.Il existe de nombreux scénarios dans la programmation en temps réel où il devient nécessaire de trier les éléments car cela rend également la recherche de un élément particulier facile car les éléments peuvent être récupérés facilement par index des tableaux directement s'ils sont triés. Les éléments qui doivent être triés peuvent être stockés dans un tableau ou une collection. La collection est de plusieurs types dans les ensembles de type Java, l'arborescence, la carte, le tas, la liste, etc., bien qu'il existe différents types d'algorithmes de tri qui sont utilisés pour trier les éléments dans un tableau de type bulle, tri par tas, tri par insertion, Tri par sélection, Tri par fusion, etc.
- Les programmeurs utilisent différents algorithmes pour trier les éléments en fonction de leurs besoins spécifiques et de la complexité des algorithmes. Ces algorithmes de tri sont implémentés grâce à l'utilisation de diverses boucles et variables pour itérer à travers celui-ci. En plus d'utiliser les algorithmes de tri pour trier les éléments dans un tableau, Java fournit la fonction intégrée de tri qui peut aider à cela et le programmeur n'a pas besoin d'être coincé dans de grandes boucles et de penser à la complexité. Oui, vous avez bien compris, en Java, la fonction sort () est utilisée pour trier les éléments stockés dans des tableaux ou des collections et cela avec une complexité très moindre de o (n (logn)). Bien que l'implémentation de la méthode dans les deux soit un peu différente.
Syntaxe des tableaux:
Arrays.sort(array_name);
Pour les collections
Collections.sort(array_name_list);
- Ici nom_tableau et liste_nom_tableau est le nom du tableau ou de la collection qui doit être trié.
- Les tableaux sont le nom des classes de Java.
- La collection est un framework en Java.
- sort () est la fonction de tri intégrée utilisée en Java.
Comment le tri est-il effectué en Java?
Voici les points suivants:
- Grâce à l'utilisation d'algorithmes de tri, le tri peut également être effectué avec des algorithmes variant d'inefficaces à efficaces et chaque algorithme a sa propre complexité temporelle et spatiale.
- Parfois, ces algorithmes sont très complexes et ne peuvent pas être utilisés dans des scénarios réels où il est nécessaire de gérer de grandes quantités de données.
- Comme mentionné ci-dessus, dans la fonction Java intégrée, sort () est utilisé pour trier tous les éléments d'un tableau et d'une collection. Selon le Java DOC officiel, Array.sort utilise le quicksort qui est le double pivot et comparativement beaucoup plus rapide que le tri rapide à simple pivot.
- L'un des plus grands avantages de ceci est qu'il fournit une complexité de O (n (logn)). Il utilise l'implémentation très stable et itérative de l'objet tableau de Merge Sort. Java fournit également une méthode pour trier le tableau dans l'ordre inverse selon l'exigence du programmeur de trier dans l'ordre croissant ou décroissant. La méthode Collections.reverseOrder () est utilisée pour trier les éléments dans l'ordre inverse ou décroissant.
- Java 8 offre également la possibilité de trier les tableaux en parallèle à l'aide du tri parallèle qui utilise le concept multithreading de Java et divise l'ensemble du tableau en parties et les fusionne après le tri.
Types de tri en Java
Ci-dessous sont mentionnées quelques-unes des façons dont le tri peut être effectué dans Tri en Java:
1. sort (array_name)
Ceci est utilisé pour trier le tableau complet par ordre croissant Par défaut, cette méthode trie les éléments du tableau par ordre croissant.
Code:
import java.util.Arrays;
public class SimpleSort
(
public static void main(String() args)
(
//Unsorted array of numbers
Integer() arr = new Integer() (100, 20, 10, 30, 80, 70, 90, 40, 50, 60);
//Sort function to sort the above array
Arrays.sort(arr);
//Printing the sorted array on console
System.out.println(Arrays.toString(arr));
)
)
Production:
2. Collection.reverseOrder ()
Cette méthode en Java est utilisée pour trier le tableau dans l'ordre inverse ou décroissant. Il existe des scénarios dans lesquels nous devons trier les éléments dans l'ordre décroissant et Java le fait via la méthode intégrée.
Code:
import java.util.Arrays;
public class ReverseSort
(
public static void main(String() args)
(
//Unsorted array of numbers
Integer() arr = new Integer() ( 100, 20, 10, 30, 80, 70, 90, 40, 50, 60);
//Sort function to sort the above array
Arrays.sort(arr, Collections.reverseOrder());
//Printing the sorted array on console
System.out.println(Arrays.toString(arr));
)
)
Production:
3. sort (int () array_name, int findex, int lindex)
S'il est nécessaire de trier une partie d'un tableau au lieu du tableau entier, Java offre la possibilité de trier ce type de tableau en spécifiant 3 paramètres, à savoir le nom du tableau, le premier index d'où le tri doit être démarré et le dernier index jusqu'au moment où le tri doit être effectué.
Code:
import java.util.Arrays;
public class ReverseSort
(
public static void main(String() args)
(
//Unsorted array of numbers
Integer() arr = new Integer() ( 100, 20, 10, 30, 80, 70, 90, 40, 50, 60);
//Sort function to sort the above array
Arrays.sort(arr, 1, 5);
//Printing the sorted array on console
System.out.println(Arrays.toString(arr));
)
Production:
4. Arrays.parllelSort (nom_tableau)
Depuis Java 8, la nouvelle API du type parallèle a été publiée. Fondamentalement, dans le tri parallèle, le tableau est divisé en 2 sous-tableaux, puis la fonction de base Array.sort () est exécutée par un thread distinct. Les tableaux triés sont ensuite fusionnés à la fin pour former le tableau entièrement trié. Cela est fait pour tirer parti de l'utilisation du multi-threading.
Code:
import java.util.Arrays;
public class ParallelSort
(
public static void main(String() args)
(
//Unsorted array of numbers
Integer() arr = new Integer() ( 100, 20, 10, 30, 80, 70, 90, 40, 50, 60);
//parallel Sort function to sort the above array
Arrays.parallelSort(arr);
//Printing the sorted array on console
System.out.println(Arrays.toString(arr));
)
)
Production:
Comme un Array.sort () normal, Arrays.parallelSort () fournit également la possibilité de trier une plage particulière de tableau ou de trier un tableau dans l'ordre inverse.
Syntaxe:
// to Sort a range of array by parallelsort
Arrays.parallelSort(array_name, findex, lindex);
// to sort an array in reverse order using parallelSort
Arrays.parallelSort(array_name, Collections.reverseOder());
5. Collection.sort ()
Cette méthode est utilisée pour trier les collections comme list, map, Set, etc. Elle utilise le tri par fusion et donne la même complexité que Array.sort (), c'est-à-dire O (n (logn)).
1. Tri d'une liste par ordre croissant
Code:
import java.util.Arrays;
import java.util.Collections;
public class ListSort
(
public static void main(String() args)
(
//Unsorted list
Integer() arr = new Integer() ( 100, 20, 10, 30, 80, 70, 90, 40, 50, 60 );
List arrList = Arrays.asList(arr);
//Sorting of list using the method
Collections.sort(arrList);
//Printing the list sorted above
System.out.println(arrList);
)
)
Production:
2. Tri d'une liste de tableaux par ordre décroissant
Code:
import java.util.Arrays;
import java.util.Collections;
public class ListSortRev
(
public static void main(String() args)
(
//Unsorted array list of Integers
Integer() arr = new Integer() (100, 20, 10, 30, 80, 70, 90, 40, 50, 60 );
List arrList = Arrays.asList(arr);
//Sorting of list using the method
Collections.sort(arrList);
//Printing the list sorted above
System.out.println(arrList);
)
)
Production:
3. Tri de l'ensemble
Il existe 3 règles de base lors du tri d'une collection 'Set' à l'aide de la méthode ci-dessus sort (array_name):
-
- Convertissez l'ensemble en liste.
- Triez la liste à l'aide de la méthode sort (array_name).
- Convertissez la liste triée résultante en ensemble.
Code:
List numList = new ArrayList(num) ;
//Sorting the list retrieved above
Collections.sort(numList);
// Converting sorted List into Set
num = new LinkedHashSet(numList);
//Printing the Resulting Set on console
System.out.println(num);
)
)
Production:
4. Trier une carte
La carte de collection en Java est une combinaison de clé et de valeur. Le tri peut donc se faire dans les deux sens, par clé ou par valeur.
- Trier une carte par clé: Voyons l'exemple ci-dessous de Tri d'une carte par clé.
Code:
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class SortHashKey
(
public static void main(String() args)
(
HashMap map = new HashMap();
map.put(80, "Akshay");
map.put(20, "Akash");
map.put(10, "Bob");
map.put(30, “Nitika");
map.put(90, "Yashi");
map.put(100, "Dragisa");
TreeMap treeMap = new TreeMap(map);
System.out.println(treeMap);
)
)
Production:
L'une des façons les plus simples de trier les éléments de la carte par clés consiste à ajouter les éléments de carte non triés dans TreeMap. TreeMap trie automatiquement les éléments dans l'ordre croissant des clés de hachage. Bien que collection.sort () puisse également être utilisé pour faire de même, il est quelque peu complexe et doit être bien codé.
- Trier une carte par valeur: Ci-dessous, un exemple de la façon dont le tri peut être effectué dans une carte en utilisant une valeur.
Code:
import java.util.HashMap;
import java.util.Map;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Map;
public class SortHashValue
(
public static void main(String() args)
(
HashMap map = new HashMap(); map.put(80, "Akshay");
map.put(20, "Akash");
map.put(10, "Bob");
map.put(30, “Nitika");
map.put(90, "Yashi");
map.put(100, "Dragisa");
LinkedHashMap sorted = new LinkedHashMap(); map.entrySet()
.stream()
.sorted(Map.Entry.comparingByValue())
.forEachOrdered(x -> sorted.put(x.getKey(), x.getValue()));
Production:
Dans l'exemple ci-dessus de tri de Map by value, nous définissons d'abord les entrées à l'aide de map.entrySet () puis le flux de ces entrées à l'aide de la méthode stream (), appelons le tableau trié à l'aide de la méthode sorted () en comparant par valeur dans le paire. pour chaque commande () est utilisée pour traverser le flux pour produire le résultat.
5. Comparable
Comparable est une interface et rend les classes comparables à ses instances.
Pour comparer les deux instances de la même classe, l'interface comparable doit être implémentée et la méthode compareTo () doit être remplacée. Les classes qui implémentent cette interface, sa liste d'objets sont triées automatiquement à l'aide des méthodes Collections.sort () et Arrays.sort ().
Code:
ArrayList list = new ArrayList();
// Adding the instance objects of class Employee in list
list.add(new Employee(10, "Akshay")));
list.add(new Employee(40, "Bob")));
list.add(new Employee(20, "Priyansh")));
list.add(new Employee(50, "Chandni")));
list.add(new Employee(70, "Yashi")));
Collections.sort(list);
// Printing the sorted list on Console
System.out.println(list);
Production:
Conclusion
Les méthodes de tri en Java expliquées ci-dessus sont utilisées en Java pour plusieurs scénarios de tableaux et de collections. Un programmeur doit garder à l'esprit comment la méthode sort () doit être utilisée pour différents types de collections. Avec Java 8, le tri peut également être effectué via Lambdas pour implémenter l'interface Comparateur, ce qui facilite le tri. Bien qu'il soit un peu difficile de les apprendre tous, il peut être facile de travailler avec eux si tous les concepts de base de Java, en particulier le streaming de données, les tableaux et les collections, sont clairs. Bien que les algorithmes de tri soient évolutifs et puissent être facilement implémentés dans d'autres langages de programmation de type Java, ils ont une complexité variable et la fonction intégrée sort () de Java facilite les choses si les concepts de base sont appris par cœur.
Articles recommandés
Ceci est un guide de tri en Java. Nous discutons ici de la façon dont le tri s'effectue en java et des types de tri en java avec différents codes et sorties. Vous pouvez également consulter nos autres articles connexes pour en savoir plus-
- JComboBox en Java
- Tri en C
- Tri en tas en C
- Tri des bulles en JavaScript
- Qu'est-ce que le tri en C ++?
- Introduction au tri en PHP
- Tri de tas en Python
- Tri par insertion en JavaScript
- Hashmap en Java
- Comparable en Java Exemple | Interface de collecte en Java