selection sort c with examples
Un examen approfondi du tri de sélection en C ++ avec des exemples.
Comme son nom l'indique, la technique de tri par sélection sélectionne d'abord le plus petit élément du tableau et le remplace par le premier élément du tableau.
Ensuite, il échange le deuxième plus petit élément du tableau avec le deuxième élément et ainsi de suite. Ainsi, à chaque passage, le plus petit élément du tableau est sélectionné et mis à sa bonne position jusqu'à ce que le tableau entier soit trié.
=> Consultez le guide de formation Perfect C ++ ici.
Ce que vous apprendrez:
- introduction
- Algorithme général
- Pseudocode pour le tri de sélection
- Illustration
- Exemple C ++
- Exemple Java
- Analyse de complexité du tri de sélection
- Conclusion
- lecture recommandée
introduction
Le tri par sélection est une technique de tri assez simple car la technique consiste uniquement à trouver le plus petit élément à chaque passage et à le placer dans la bonne position.
Le tri par sélection fonctionne efficacement lorsque la liste à trier est de petite taille, mais ses performances sont affectées gravement à mesure que la liste à trier augmente en taille.
Par conséquent, nous pouvons dire que le tri par sélection n'est pas recommandé pour les listes de données plus volumineuses.
Algorithme général
L'algorithme général pour le tri de sélection est donné ci-dessous:
quelle est la meilleure application vr
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 : Swap A (K) avec A (POS)
(Fin de la boucle)
Étape 4 : SORTIR
La plus petite routine (A, K, N, POS)
- Étape 1 : (initialize) set smallestElem = A (K)
- Étape 2 : (initialiser) définir POS = K
- Étape 3 : pour J = K + 1 à N -1, répéter
si le plus petit élément> A (J)
définir smallestElem = A (J)
définir POS = J
(si fin)
(Fin de la boucle) - Étape 4 : retourner POS
Pseudocode pour le tri de sélection
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) Un exemple illustrant cet algorithme de tri par sélection est présenté ci-dessous.
Illustration
La représentation tabulaire de cette illustration est présentée ci-dessous:
Liste non triée Le moindre élément Liste triée {18,10,7,20,2} deux {} {18,10,7,20} sept {deux} {18,10,20} dix {2.7} {18.20} 18 {2,7,10) {vingt} vingt {2,7,10,18} {} {2,7,10,18,20}
À partir de l'illustration, nous voyons qu'à chaque passage, le plus petit élément suivant est mis à sa position correcte dans le tableau trié. D'après l'illustration ci-dessus, nous voyons que pour trier un tableau de 5 éléments, quatre passes étaient nécessaires. Cela signifie qu'en général, pour trier un tableau de N éléments, nous avons besoin de N-1 passes au total.
Ci-dessous est l'implémentation de l'algorithme de tri de sélection en C ++.
Exemple C ++
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<10;i++) { cout< Production:
Liste d'entrée des éléments à trier
11 5 2 20 42 53 23 34101 22
La liste triée des éléments est
2 5 11 20 22 23 34 42 53 101
Nombre de passes nécessaires pour trier le tableau: 10
Comme indiqué dans le programme ci-dessus, nous commençons le tri par sélection en comparant le premier élément du tableau avec tous les autres éléments du tableau. À la fin de cette comparaison, le plus petit élément du tableau est placé en première position.
Dans la passe suivante, en utilisant la même approche, le plus petit élément suivant du tableau est placé dans sa position correcte. Cela continue jusqu'à N éléments, ou jusqu'à ce que le tableau entier soit trié.
Exemple Java
Ensuite, nous implémentons la technique de tri par sélection dans le langage Java.
class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println('
Input list to be sorted...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println('
printing sorted elements...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j) Production:
Liste d'entrée à trier…
11 5 2 20 42 53 23 34101 22
impression des éléments triés…
2 5 11 20 22 23 34 42 53 101
Dans l'exemple java ci-dessus également, nous appliquons la même logique. 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é.
Ainsi, le tri par sélection est l'algorithme le plus simple à implémenter, car nous devons simplement trouver à plusieurs reprises le plus petit élément suivant du tableau et l'échanger avec l'élément à sa position appropriée.
Analyse de complexité du tri de sélection
Comme on le voit dans le pseudo-code ci-dessus pour le tri par sélection, nous savons que le tri par sélection nécessite deux boucles for imbriquées l'une dans l'autre pour se compléter. Une boucle for parcourt tous les éléments du tableau et nous trouvons l'index d'élément minimum en utilisant une autre boucle for qui est imbriquée dans la boucle for externe.
Par conséquent, étant donné une taille N du tableau d'entrée, l'algorithme de tri de sélection a les valeurs de temps et de complexité suivantes.
Pire complexité temporelle des cas O (n 2); O (n) swaps Meilleure complexité temporelle O (n 2); O (n) swaps Complexité temporelle moyenne O (n 2); O (n) swaps Complexité spatiale O (1)
La complexité temporelle de O ( n deux) est principalement dû à l'utilisation de deux boucles for. Notez que la technique de tri par sélection ne prend jamais plus de O (n) swaps et est bénéfique lorsque l'opération d'écriture mémoire s'avère coûteuse.
Conclusion
Le tri par sélection est encore une autre technique de tri la plus simple qui peut être facilement mise en œuvre. Le tri par sélection fonctionne mieux lorsque la plage des valeurs à trier est connue. Ainsi, en ce qui concerne le tri des structures de données à l'aide du tri par sélection, nous ne pouvons trier que des structures de données linéaires et de taille finie.
Cela signifie que nous pouvons trier efficacement les structures de données telles que les tableaux en utilisant le tri par sélection.
Dans ce didacticiel, nous avons discuté en détail du tri par sélection, y compris l'implémentation du tri par sélection à l'aide des langages C ++ et Java. La logique derrière le tri de sélection est de trouver le plus petit élément de la liste à plusieurs reprises et de le placer dans la bonne position.
Dans le prochain tutoriel, nous apprendrons en détail le tri par insertion, qui est considéré comme une technique plus efficace que les deux autres techniques dont nous avons discuté jusqu'à présent, à savoir le tri par bulles et le tri par sélection.
=> Vérifiez ici pour voir de A à Z des didacticiels de formation C ++ ici.
lecture recommandée
- Shell tri en C ++ avec des exemples
- Méthode MongoDB Sort () avec exemples
- Commande de tri Unix avec syntaxe, options et exemples
- Tri à bulles en C ++ avec des exemples
- Tri par insertion en C ++ avec des exemples
- Fusionner le tri en C ++ avec des exemples
- Tri de tas en C ++ avec des exemples
- Tri rapide en C ++ avec des exemples
