Sélection Tri dans Java Programme avec exemple
Équipe éditoriale
⚡ Résumé intelligent
Tri de la sélection dans Java parcourt à plusieurs reprises la partie non triée d'un tableau, trouve la plus petite valeur restante et l'insère dans la position, terminant le travail avec au plus n-1 échanges quel que soit l'ordre d'entrée.
Comment fonctionne le tri par sélection ?
Selection Sort implémente un algorithme de tri simple comme suit :
- L'algorithme recherche à plusieurs reprises l'élément le plus bas.
- Échanger l'élément actuel avec un élément ayant la valeur la plus basse
- À chaque itération/passe de tri par sélection, les éléments sont échangés.
Chaque passage traite donc le tableau L'algorithme divise le système en deux régions : un bloc trié qui s'étend de gauche à droite et un bloc non trié qui se réduit de droite à gauche. Il parcourt le bloc non trié, mémorise l'indice de la plus petite valeur rencontrée et échange cette valeur avec la première position du bloc non trié.
Puisqu'un seul échange a lieu par passage, un tableau de n éléments est ordonné après au plus n-1 échanges. C'est cette propriété qui distingue cette routine des autres routines de niveau débutant. Java les algorithmes de tri, qui déplacent les données beaucoup plus fréquemment.
Le tracLe tableau ci-dessous suit exactement l'exemple {860, 8, 200, 9} tel que le programme de la section suivante l'imprime lors de son exécution.
| Passé | Comparaisons imprimées | Valeur minimale trouvée | Tableau après l'échange |
|---|---|---|---|
| Commencer | - | - | 860 8 200 9 |
| 1 | 860 et 8, 8 et 200, 8 et 9 | 8 | 8 860 200 9 |
| 2 | 860 et 200, 200 et 9 | 9 | 8 9 200 860 |
| 3 | 200 et 860 | 200 | 8 9 200 860 |
Deux détails à ce sujet tracIl convient de s'attarder sur ces points. Premièrement, le troisième passage signale toujours un échange même si l'ordre reste inchangé, car la plus petite valeur restante se trouve déjà à l'index actuel et le programme échange l'élément avec lui-même. Deuxièmement, le nombre de comparaisons diminue d'une unité à chaque passage (trois, puis deux, puis une), ce qui explique les chiffres de complexité présentés plus bas.
Java Programme pour implémenter le tri par sélection
La classe ci-dessous, nommée SelectionSortAlgo, se trouve dans le package com.guru99. La méthode main() déclare le tableau d'exemple, l'affiche, le transmet à selection() pour le tri, puis l'affiche à nouveau. La fonction auxiliaire printArray() écrit tous les éléments sur une seule ligne, ce qui produit le journal détaillé des opérations.
Dans la fonction selection(), la boucle externe marque la limite entre les régions triées et non triées, la variable index contient la position de la plus petite valeur vue jusqu'à présent, et les trois affectations à la fin de chaque passage effectuent l'échange.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Sortie :
La compilation et l'exécution de la classe produisent le journal de la console ci-dessous, avec un bloc de sortie par passe.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Deux problèmes piègent les débutants lorsqu'ils exécutent cet exemple pour la première fois. Parce que le fichier déclare package com.guru99;, la source doit se trouver dans un correspondant com/guru99 Le répertoire doit être spécifié, sinon le compilateur signale une incompatibilité de nom de package ou de classe. La classe doit alors être lancée par son nom complet. java com.guru99.SelectionSortAlgo, parce que simple java SelectionSortAlgo Lève une erreur NoClassDefFoundError.
Les limites de boucle constituent l'autre piège courant. La boucle extérieure s'arrête à array.length - 1 et la boucle intérieure commence à i + 1; la modification de l'une ou l'autre limite produit un passage vide supplémentaire ou une exception ArrayIndexOutOfBoundsException.
Complexité temporelle et spatiale du tri par sélection
La boucle interne du programme s'exécute toujours jusqu'à la fin du tableau ; l'algorithme effectue donc le même nombre de comparaisons, quelles que soient les données. Pour un tableau de n éléments, ce nombre est de n(n-1)/2, soit six pour l'exemple à quatre éléments. L'affichage ci-dessus indique bien six lignes de comparaison.
| Témoignage client | Comparaisons | Swaps | Complexité temporelle | Espace auxiliaire |
|---|---|---|---|---|
| Meilleur (tableau déjà trié) | n (n-1) / 2 | n-1 | O(n²) | O (1) |
| Moyenne (ordre aléatoire) | n (n-1) / 2 | n-1 | O(n²) | O (1) |
| Pire (tri inversé) | n (n-1) / 2 | n-1 | O(n²) | O (1) |
Trois conséquences découlent de cette rangée uniforme de chiffres :
- Le tri par sélection n'est pas adaptatif. Le coût d'entrée trié est exactement le même que celui d'une entrée inversée ; il n'existe donc pas de raccourci permettant une sortie anticipée. tri à bulles des offres.
- Le nombre d'échanges est le point fort de cet algorithme. Au maximum n-1 échanges ont lieu, ce qui est bien inférieur au nombre quadratique de mouvements que peuvent effectuer d'autres algorithmes de tri simples.
- L'utilisation de la mémoire est constante. Seuls les compteurs de boucle et les deux variables temporaires index et smallerNumber sont nécessaires ; l'espace auxiliaire est donc O(1) et le tri s'effectue sur place.
La croissance quadratique représente la limite pratique. Doubler la taille du tableau quadruple approximativement le travail de comparaison ; le tri par sélection convient donc à l’enseignement, aux petits tableaux et au code embarqué plutôt qu’aux ensembles de données de production, où les algorithmes en O(n log n) sont le choix approprié.
Avantages et inconvénients du tri par sélection
Comprendre où l'algorithme est utile et où il est nuisible permet de décider plus facilement quand son utilisation est justifiée.
Avantages
- La logique est concise et lisible, c'est pourquoi elle constitue un exercice de tri initial standard. tri par insertion.
- Le tri s'effectue sur place, ce qui évite l'allocation d'un second tableau et l'augmentation de la consommation de mémoire avec l'entrée.
- Il effectue au maximum n-1 écritures sur le tableau, ce qui est important sur les supports de stockage où les écritures sont lentes ou usent le support.
- Son temps d'exécution est parfaitement prévisible, car le nombre de comparaisons dépend uniquement de la longueur du tableau.
Désavantages
- Chaque cas est O(n²), donc l'algorithme ne s'adapte pas aux grandes collections.
- Il ne peut pas détecter un tableau déjà trié et ne se termine donc jamais prématurément.
- La forme classique présentée ci-dessus est instable, de sorte que deux valeurs égales peuvent se retrouver dans l'ordre inverse.
- Elle se compare plus souvent que le tri par insertion sur des données presque ordonnées, où le tri par insertion tend vers un temps linéaire.
En résumé, choisissez le tri par sélection lorsque le tableau est petit et que chaque écriture est coûteuse, et évitez-le lorsque l'ensemble de données est volumineux ou déjà presque trié.
Tri par sélection vs BubblTri par insertion vs tri par insertion
Ces trois algorithmes sont des tris par comparaison en place quadratiques, mais ils se comportent différemment une fois que la forme de l'entrée change.
| Critère | Tri de sélection | Bubble tri | Tri par insertion |
|---|---|---|---|
| temps de meilleur cas | O(n²) | O (n) | O (n) |
| Temps moyen et dans le pire des cas | O(n²) | O(n²) | O(n²) |
| Des échanges ou des décalages dans le pire des cas | n-1 échanges | n(n-1)/2 échanges | Jusqu'à n(n-1)/2 décalages |
| Stable | Non | Oui | Oui |
| Adapté aux entrées triées | Non | Oui | Oui |
| Espace auxiliaire | O (1) | O (1) | O (1) |
| Utilisation typique | Le moins d'écritures requises | Enseignement et repérage de données triées | tableaux de petite taille ou presque triés |
Le tableau illustre une réponse courante en entretien d'embauche. Le tri par sélection l'emporte sur le nombre d'échanges, le tri à bulles sur la reconnaissance des données déjà triées, et le tri par insertion est généralement le plus rapide des trois en pratique, car les données réelles sont souvent partiellement triées. Aucun de ces tris ne rivalise avec le tri fusion ou le tri rapide dès que le tableau dépasse quelques dizaines d'éléments.
