Tri de sélection en Java

Le tri par sélection en Java est une méthode de tri qui trouve continuellement le plus petit élément dans la partie non triée et le conserve au début (pour le tri par ordre croissant). Le processus sera répété jusqu'à ce que le tableau d'entrée soit trié. De plus, dans Selection Sort, nous diviserons le tableau d'entrée en deux sous-tableaux où un tableau est utilisé pour les éléments triés et l'autre tableau pour les éléments non triés. Au début, il n’y aura aucun élément dans le sous-tableau trié. Voyons le fonctionnement du tri par sélection en détail dans la section suivante.

Comment fonctionne le tri par sélection en Java

Le tri par sélection fonctionne de manière simple en conservant deux sous-tableaux du tableau d'entrée. Ce sont :

Commencez votre cours de développement de logiciels libres

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

• Sous-tableau trié pour conserver les éléments triés
• Sous-tableau non trié pour conserver les éléments non triés.

Algorithme

Voici l'algorithme utilisé pour le tri par sélection

1. Réglez le pointeur minimum (MIN) sur l'emplacement 0.
2. Trouver le plus petit élément de la liste des éléments du tableau

• Échangez l'élément minimum avec l'emplacement 0

1. Déplacez le pointeur MIN vers la position suivante
2. Répétez le processus jusqu'à ce que le tableau d'entrée soit trié.

Comprenons le tri par sélection avec un exemple. Voici le tableau d'entrée qui doit être trié. Les éléments de couleur bleu gras feront partie du tableau trié.

Étape 1 : Réglez le pointeur MIN sur le premier emplacement. Ainsi, le pointeur MIN pointe vers 15.

Le plus petit : = 15

Étape 2 : Trouvez le plus petit élément en le comparant avec le reste des éléments. En comparant 15 et 21, 15 est le plus petit. Donc, le plus petit ne changera pas dans ce cas.

Le plus petit : = 15

En comparant 15 et 6, 6 est le plus petit.

Le plus petit : = 6

En comparant 6 et 3, 3 est le plus petit.

Le plus petit : = 3

3 sera plus petit dans ce cas également, car 19 est supérieur à 3.

Le plus petit : = 3

Le plus petit : = 3

Enfin, dans cette itération, 3 se révèle être le plus petit.

Étape 3 : Échangez le plus petit élément avec l'élément à l'emplacement 0.

Étape 4 : Incrémentez le pointeur MIN jusqu'à la position suivante.

Étape 5 : Trouvez le prochain plus petit élément en le comparant avec le reste des éléments.

Le plus petit : = 21

Le plus petit : = 6

Le plus petit : = 6

Le plus petit : = 6

Le plus petit : = 6

Étape 6 : Échangez le plus petit élément avec l'élément à l'emplacement 1.

Répétez le processus jusqu'à ce qu'un tableau trié soit formé, comme indiqué ci-dessous.

Exemples d'implémentation du tri par sélection en Java

Comme déjà mentionné ci-dessus, le tri de sélection est basé sur la recherche du minimum et l'échange. Voyons maintenant comment implémenter le tri par sélection en utilisant Java.

Programme Java pour trier les éléments d'un tableau à l'aide du tri par sélection

Code :

import java.util.*;
public class SelSortExample {
//Method that implements Selectionsort
public static void selsort(int[] arr)
{
int n=arr.length; //length of the array
for(int i=0;i<n-1;i++)
{
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j<n;j++)
{
System.out.println("Comparing "+ arr[MIN] + " and " + arr[j]);
if(arr[j]<arr[MIN])
{
System.out.println(arr[MIN] + " is greater than " + arr[j] );
MIN=j;
}
}
//Swap the smallest element with element in MIN position
int temp=arr[i];
arr[i]=arr[MIN];
arr[MIN]=temp;
}
}
public static void main(String[] args) {
int[] arr= {15,21,6,3,19,20}; // input array
System.out.println("Elements in the array before Sorting: "+ Arrays.<em>toString</em>(arr));
<em>selsort</em>(arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays.<em>toString</em>(arr));
}
}

Exemple de sortie :

Dans le programme ci-dessus, nous avons deux méthodes : les méthodes principales et la méthode de tri de vente. La méthode principale appelle la méthode de tri de vente en passant le tableau d'entrée comme argument. L'élément minimum sera identifié et échangé avec l'élément pointé par MIN.

The selection sort can also be used where the input array is not defined in code. Let us see how it works using the below program.

Java Program to Sort the Elements using Selection Sort

Code:

import java.util.*;
public class SelectionSortExample
{
public static void main(String args[])
{
int n, i, j, tempvar;
Scanner <u>sc</u> = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array[] = new int[n]; //<u>initialising</u> the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i<n; i++)
{
array[i] = sc.nextInt();
}
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(array[i] > array[j])
{
tempvar = array[i];
array[i] = array[j];
array[j] = tempvar;
}
}
}
System.out.print("Array after Sorting is :\n");
for(i=0; i<n; i++)
{
System.out.print(array[i]+ " ");
}
}
}

Sample Output:

Here, the input elements given by the user will be compared with the temporary variable and swapped. The process will be repeated until a sorted array is formed.

Performance of Selection Sort

This sorting technique is used for its simplicity and certain other performance advantages over other more sorting techniques.

Conclusion

The selection sort does not work efficiently on large lists as it consumes more time for comparison. Selection sort is a method in which an input array will be divided into two subarrays in order to keep them sorted and unsorted elements. The minimum element in the array will be swapped with the element in the first position, and the process continues until a sorted array is formed.

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!