Introduction au 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 dans l'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 pour les éléments non triés. Au début, il n'y aura aucun élément dans le sous-tableau trié. Voyons en détail le fonctionnement du tri de sélection dans la section suivante.
Fonctionnement du tri par sélection en Java
Le tri par sélection fonctionne d'une manière simple où il conserve deux sous-réseaux du tableau d'entrée. Elles sont:
- 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 de sélection
- Réglez le pointeur minimum (MIN) sur l'emplacement 0.
- Recherchez le plus petit élément dans la liste des éléments du tableau
- Échangez l'élément minimum avec l'emplacement 0
- Déplacer le pointeur MIN à la position suivante
- Répétez le processus jusqu'à ce que le tableau d'entrée soit trié.
Comprenons le tri de la sélection avec un exemple. Voici le tableau d'entrée qui doit être trié. Les éléments de couleur Bold Blue feront partie du tableau trié.
Étape 1 : placez le pointeur MIN sur le premier emplacement. Ainsi, le pointeur MIN pointe sur 15.
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.
Plus petit: = 15
En comparant 15 et 6, 6 est le plus petit.
Plus petit: = 6
En comparant 6 et 3, 3 est le plus petit.
Plus petit: = 3
3 sera également plus petit dans ce cas, puisque 19 est supérieur à 3.
Plus petit: = 3
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: augmentez le pointeur MIN à la position suivante.
Étape 5: Trouvez le plus petit élément suivant en le comparant avec le reste des éléments.
Plus petit: = 21
Plus petit: = 6
Plus petit: = 6
Plus petit: = 6
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 illustré ci-dessous.
Exemples pour implémenter le tri de sélection en Java
Comme déjà mentionné ci-dessus, le tri par sélection est basé sur la recherche du minimum et l'échange. Voyons maintenant comment implémenter le tri de sélection à l'aide de Java.
Programme Java pour trier les éléments d'un tableau à l'aide du tri par sélection
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 (
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 (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
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. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)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 (
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 (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
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. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)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 (
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 (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
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. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)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 (
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 (
System.out.println("Comparing "+ arr(MIN) + " and " + arr(j));
if(arr(j) (
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. toString (arr));
selsort (arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays. toString (arr));
)
)
Exemple de sortie:
Dans le programme ci-dessus, nous avons deux 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.
Le tri par sélection peut également être utilisé lorsque le tableau d'entrée n'est pas défini dans le code. Voyons comment cela fonctionne en utilisant le programme ci-dessous.
Programme Java pour trier les éléments à l'aide du tri par sélection
import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = 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); //initialising 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 (
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 (
for(j=i+1; 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 (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = 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); //initialising 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 (
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 (
for(j=i+1; 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 (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = 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); //initialising 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 (
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 (
for(j=i+1; 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 (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = 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); //initialising 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 (
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 (
for(j=i+1; 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 (
System.out.print(array(i)+ " ");
)
)
)import java.util.*;
public class SelectionSortExample
(
public static void main(String args())
(
int n, i, j, tempvar;
Scanner sc = 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); //initialising 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 (
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 (
for(j=i+1; 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 (
System.out.print(array(i)+ " ");
)
)
)
Exemple de sortie:
Ici, les éléments d'entrée donnés par l'utilisateur seront comparés à la variable temporaire et échangés. Le processus sera répété jusqu'à ce qu'un tableau trié soit formé.
Performances du tri de sélection
Cette technique de tri est utilisée pour sa simplicité et certains autres avantages de performance par rapport à d'autres techniques de tri plus.
Conclusion
Le tri par sélection ne fonctionne pas efficacement sur les grandes listes car il consomme plus de temps pour la comparaison. Le tri par sélection est une méthode dans laquelle un tableau d'entrée sera divisé en deux sous-tableaux afin de conserver les éléments triés et non triés. L'élément minimum dans le tableau sera échangé avec l'élément dans la première position et le processus se poursuit jusqu'à ce qu'un tableau trié soit formé.
Articles recommandés
Ceci est un guide pour le tri de sélection en Java. Nous discutons ici de l'introduction, du fonctionnement et des performances du tri de sélection ainsi que de quelques exemples. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Fusionner le tri en Java
- Tri de tas en Java
- Copier le constructeur en Java
- Motifs d'étoiles en Java
- Tri de tas en Python