selection sort java selection sort algorithm examples
Ce didacticiel expliquera tout sur le tri de sélection en Java avec l'algorithme de tri de sélection, le code Java, l'implémentation en Java et les exemples Java:
La technique de tri par sélection est une méthode dans laquelle le plus petit élément du tableau est sélectionné et échangé avec le premier élément du tableau. Ensuite, le deuxième élément le plus petit du tableau est échangé avec le deuxième élément et vice versa.
=> Cliquez ici pour voir de A à Z des didacticiels de formation Java ici.
Ce que vous apprendrez:
Tri par sélection en Java
De cette façon, le plus petit élément du tableau est sélectionné à plusieurs reprises et mis à sa bonne position jusqu'à ce que le tableau entier soit trié.
Deux sous-tableaux sont conservés pour le tri par sélection:
- Sous-tableau trié: Dans chaque itération, l'élément minimum est trouvé et placé dans sa bonne position. Ce sous-tableau est trié.
- Sous-tableau non trié: Les éléments restants qui ne sont pas triés.
Le tri par sélection est une technique de tri simple et facile. La technique consiste uniquement à trouver le plus petit élément à chaque passage et à le placer dans la bonne position. Le tri par sélection est idéal pour les petits ensembles de données car il trie efficacement le plus petit ensemble de données.
Ainsi, nous pouvons dire que le tri par sélection n'est pas conseillé pour les listes de données plus volumineuses.
Algorithme de tri par sélection
L'algorithme général pour le tri de sélection est donné ci-dessous:
Tri par sélection (A, N)
Étape 1 : Répétez les étapes 2 et 3 pour K = 1 à N-1
Étape 2 : Appel de la routine la plus petite (A, K, N, POS)
Étape 3 :
Remplacer A (K) par A (POS)
(Fin de la boucle)
Étape 4 : SORTIR
La plus petite routine (A, K, N, POS)
Étape 1 : (initialize) set smallestItem = A (K)
Étape 2 : (initialiser) définir POS = K
Étape 3 :
pour J = K + 1 à N -1, répéter
si le plus petitItem> A (J)
set smallestItem = A (J)
définir POS = J
(si fin)
(Fin de la boucle)
Étape 4 : retourner POS
Comme vous pouvez le voir, la routine de recherche du plus petit nombre est appelée lors du parcours de l'ensemble de données. Une fois que le plus petit élément est trouvé, il est placé dans la position souhaitée.
meilleur logiciel de mise au point de pc gratuit
Pseudocode pour le tri de sélection
Le pseudo-code de l'algorithme de tri par sélection est donné ci-dessous.
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) Illustrons maintenant le tri d'un tableau en utilisant le tri par sélection.
Exemple de tri par sélection
Considérez le tableau suivant qui doit être trié comme exemple de tri par sélection.
Ci-dessous, une représentation tabulaire pour l'illustration:
Liste non triée Le moindre élément Liste triée {17,10,7,29,2} deux {} {17,10,7,29} 7 {deux} {17,10,29} dix {2.7} {17.29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
À partir de l'illustration, nous voyons qu'à chaque passage, le plus petit élément suivant est mis à sa position correcte dans le tableau trié. En général, pour trier un tableau de N éléments, nous avons besoin de N-1 passes au total.
Implémentation du tri par sélection en Java
Voyons maintenant le programme Java pour implémenter le tri par sélection.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Production:
Baie d’origine: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Tableau trié: (2, 5, 7, 10, 15, 20, 23, 34, 42)
Dans l'exemple java ci-dessus, nous trouvons à plusieurs reprises le plus petit élément du tableau et le mettons dans le tableau trié jusqu'à ce que le tableau entier soit complètement trié.
Sélection Trier la liste liée en Java
Vous trouverez ci-dessous une liste chaînée et nous devons la trier en utilisant le tri par sélection. Pour ce faire, nous utiliserons l'approche récursive du tri par sélection. Au lieu d'échanger la partie données du nœud, nous échangerons les nœuds et réalignerons les pointeurs.
Donc, si la liste chaînée est donnée comme suit:
Ci-dessous, le programme Java qui implémente le tri ci-dessus.
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data Production:
Liste liée d'origine:
7 9 3 5 1 11
Liste liée après tri:
1 3 5 7 9 11
convertisseur youtube en mp3 gratuit en toute sécurité
Notez que dans le programme ci-dessus, nous avons réaligné les liens des nœuds au lieu de trier uniquement le composant de données du nœud.
Questions fréquemment posées
Q # 1) Comment fonctionne le tri par sélection?
Répondre: Le tri par sélection fonctionne en conservant deux sous-tableaux. L'élément minimum du sous-tableau non trié est placé à sa bonne position dans un sous-tableau trié. Ensuite, le deuxième élément le plus bas est placé dans sa position correcte. De cette façon, le tableau entier est trié en sélectionnant un élément minimum à chaque itération.
Q # 2) Quelle est la complexité du tri de sélection?
Répondre: La complexité globale du tri par sélection est O (ndeux), ce qui en fait l'algorithme inefficace sur des ensembles de données plus volumineux. D'autres techniques de tri sont plus efficaces.
Q # 3) Quels sont les avantages et les inconvénients du tri par sélection?
Répondre: Le tri par sélection est la technique de tri sur place et ne nécessite donc pas de stockage supplémentaire pour stocker les éléments intermédiaires.
Il fonctionne efficacement sur des structures de données plus petites ainsi que sur les ensembles de données qui sont presque triés.
L'inconvénient majeur de la technique de tri par sélection est qu'elle fonctionne très mal lorsque la taille de la structure de données augmente. Cela devient non seulement plus lent, mais diminue également l'efficacité.
Q # 4) Combien de swaps y a-t-il dans le tri de sélection?
Répondre: La technique de tri par sélection prend le nombre minimum de swaps. Dans le meilleur des cas, lorsque le tableau est trié, le nombre de swaps dans le tri de sélection est de 0.
Q # 5) Le tri par sélection est-il plus rapide que le tri par insertion?
Répondre: Le tri par insertion est plus rapide, plus efficace et plus stable. Le tri par sélection n'est plus rapide que pour les ensembles de données plus petits et les structures partiellement triées.
Conclusion
Le tri par sélection est une technique qui fonctionne en sélectionnant l'élément minimum tout en parcourant le tableau. Pour chaque passe / itération, l'élément minimum suivant dans l'ensemble de données est sélectionné et placé dans sa position appropriée.
La technique de tri par sélection fonctionne efficacement lorsque le nombre d'éléments dans l'ensemble de données est plus petit, mais elle commence à mal fonctionner à mesure que la taille de l'ensemble de données augmente. Cela devient inefficace par rapport aux autres techniques similaires comme le tri par insertion.
Dans ce didacticiel, nous avons implémenté des exemples pour trier les tableaux et les listes liées à l'aide du tri par sélection.
=> Visitez ici pour voir la série de formations Java pour tous.
lecture recommandée
- Comment trier un tableau en Java - Tutoriel avec des exemples
- Sélection de tri en C ++ avec des exemples
- Tutoriel Java Array Length avec des exemples de code
- Méthode MongoDB Sort () avec exemples
- Jagged Array In Java - Tutoriel avec des exemples
- Commande de tri Unix avec syntaxe, options et exemples
- Inverser un tableau en Java - 3 méthodes avec des exemples
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
