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 facilite également la recherche d'un élément particulier car les éléments peuvent être facilement récupérés par un index de tableaux directement s'ils sont triés. Les éléments qui doivent être triés peuvent être stockés soit dans un tableau, soit dans une collection. La collection est de nombreux types dans des ensembles, des arbres, des cartes, des tas, des listes, etc. de type Java, bien qu'il existe différents types d'algorithmes de tri qui sont utilisés pour trier les éléments dans un tri à bulles de type tableau, 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 exigences 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 les parcourir. En plus d'utiliser les algorithmes de tri pour trier les éléments d'un tableau, Java fournit la fonction de tri intégrée, ce qui peut aider, et le programmeur n'a pas besoin d'être coincé dans de grandes boucles et de réfléchir à la complexité. Oui, vous avez bien entendu, en Java, la fonction sort() est utilisée pour trier les éléments stockés soit dans des tableaux, soit dans des collections et cela avec très moins de complexité o(n(logn)). Cependant, la mise en œuvre de la méthode dans les deux cas est un peu différente.

Syntaxe pour les tableaux :

Arrays.sort(array_name);

Pour les collections

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Collections.sort(array_name_list);

• Ici array_name et array_name_list sont le nom du tableau ou de la collection qui doit être triée.
• 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 intégrée Java, 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 tri rapide, qui est le double pivot et comparativement beaucoup plus rapide que le tri rapide à un seul 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 les exigences du programmeur, qui doit trier par ordre croissant ou décroissant. La méthode Collections.reverseOrder() est utilisée pour trier les éléments par 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

Vous trouverez ci-dessous quelques-unes des manières par lesquelles le tri peut être effectué dans le 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));
}
}

Sortie :

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

Sortie :

3. sort(int[ ] array_name, int findex, int lindex)

S'il est nécessaire de trier une partie d'un tableau au lieu de l'ensemble du tableau, Java offre la possibilité de trier ce type de tableau en spécifiant 3 paramètres, c'est-à-dire le nom du tableau, le premier index à partir duquel 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));
}
}

Sortie :

4. Arrays.parllelSort(array_name)

From Java 8, the new API of the parallel sort has been released. Basically, in Parallel sort, the array is divided into 2 sub-arrays, and then the basic Array.sort() function is performed by a separate thread. The sorted arrays are then merged in the end to form the fully sorted array. This is done to leverage the use of 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));
}
}

Output:

Like a normal Array.sort(), Arrays.parallelSort() also provides the facility to sort a particular range of array or sorting an array in reverse order.

Syntax:

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

This method is used to sort the collections like list, map, Set, etc. It uses the merge sort and gives the same complexity as Array.sort(), i.e. O(n(logn)).

1. Sorting a List in ascending order

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<Integer> arrList = Arrays.asList(arr);
//Sorting of list using the method
Collections.sort(arrList);
//Printing the list sorted above
System.out.println(arrList);
}
}

Output:

2. Sorting an Array List in descending order

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<Integer> arrList = Arrays.asList(arr);
//Sorting of list using the method
Collections.sort(arrList);
//Printing the list sorted above
System.out.println(arrList);
}
}

Output:

3. Sorting of Set

There are 3 basic rules while sorting a collection ‘Set’ using the above method sort(array_name):

1. 1. Convert the Set into the list.
   2. Sort the list using the method sort(array_name).
   3. Convert the resulting sorted List back to Set.

Code:

List<Integer> numList = new ArrayList<Integer>(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);
}
}

Output:

4. Sort a Map

Collection Map in Java is a combination of key and value So sorting can be done both ways, either through key or by value.

• Sort a Map by Key: Let’s see the below example of Sorting a Map by Key.

Code:

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class SortHashKey
{
public static void main(String[] args)
{
HashMap<Integer, String> 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<Integer, String> treeMap = new TreeMap<>(map);
System.out.println(treeMap);
}
}

Output:

One of the easiest ways to sort the elements of the Map by Keys is by adding the unsorted map elements in the TreeMap. TreeMap automatically sorts the elements in the ascending order of Hash Keys. Though collection.sort() can also be used to do the same, it is somewhat complex and needs to be coded well.

• Sort a Map by Value: Below mentioned is an example of how the sorting can be done in a Map using value.

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<Integer, String> 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<Integer, String> sorted = new LinkedHashMap<>(); map.entrySet()
.stream()
.sorted(Map.Entry.comparingByValue())
.forEachOrdered(x -> sorted.put(x.getKey(), x.getValue()));

Output:

In the above example of sorting of Map by value, firstly we set the entries using the map.entrySet() and then stream of those entries using stream() method, call the sorted array using sorted() method by comparing by value in the pair. for each ordered() is used to traverse the stream to produce the result.

5. Comparable

Comparable is an Interface, and it makes the classes comparable to its instances.

To compare the two instances of the same class, Comparable interface needs to be implemented, and the method compareTo() needs to be overridden. The classes that implement this interface, its list of objects are sorted automatically using the method Collections.sort() and Arrays.sort().

Code:

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

Output:

Conclusion

The Sorting in Java methods used in Java for multiple scenarios of Arrays and Collections are explained above. A programmer needs to keep in mind how the sort() method should be used for different Collection types. With Java 8, sorting can also be done through Lambdas to implement the Comparator interface, which makes the sorting easier. Though it is a bit difficult to learn all of them, it can be easy working with them if all the basic concepts of Java, especially data streaming, Arrays, and Collections, are clear. Though sorting Algorithms are evergreen and can be easily implemented in Java-like other programming languages, they have varying complexity, and the in-built function sort() of Java makes things easier if the basic concepts are learned by heart.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!