Algorithme de tri par selection - testprog.ru

Algorithmes de tri - liafa

La sous-suite ( a 1, a 2,., a k, a k1) est maintenant triée et l'on recommence la boucle de rechercjhe du minimum sur la nouvelle sous-liste ( a k2, a k3,., a n) etc. Pour les deux versions 1 et 2 : Le nombre de comparaisons " si Tab j Tab m alors " est une valeur qui ne dépend que de la longueur n de la liste ( n est le nombre d'éléments du tableau ce nombre est égal au nombre de fois que les itérations s'exécutent, le comptage montre que la boucle. La complexité au pire en nombre d'échanges de la version 1 est de l'ordre de n, que l'on écrit O(n). Pour la version 2 L'échange a lieu systématiquement dans la boucle principale " pour i de 1 jusquà n-1 faire " qui s'exécute n-1 fois : La complexité en nombre d'échanges de cellules de la version 2 est de l'ordre.

Résultat de l'exécution du programme précédent : F) Classe Java (tableau d'entiers) class ApplicationTriSelect static int table new int 20 ; /letableauètrierenattribut staticvoid Impression /Affichagedutableau int n table. Length - 1 ;for( int i 1 ; i n ; i ) int ( tablei intln staticvoid Initialisation /remplissagealéatoiredutableau int n table. Exemple : soit la liste à 6 éléments ( 5, 4, 2, 3, 7,1 appliquons la version 2 du tri par sélection sur cette liste d'entiers. Visualisons les différents états de la liste pour la première itération externe contrôlée par i (i 1) et pour les itérations internes contôlées par l'indice j (de j 2. La complexité en nombre de comparaison est égale à la somme des n-1 termes suivants (i 1,.i n-1) C (n-2)1 (n-3)1.10 (n-1 n-2).1 n.(n-1 2 (c'est la somme des n-1 premiers entiers). Au lieu de travailler sur les contenus des cellules de la table, nous travaillons sur les indices, ainsi lorsque a j est plus petit que a i nous mémorisons l'indice "j" du minimum dans une variable " m j ; " plutôt que le minimum lui-même.

A la fin de la boucle interne " pour j de i1 jusquà n faire " la variable m contient l'indice de min( a i1, a k2,., a n) et l'on permute l'élément concerné (d'indice m) avec l'élément frontière a i : Algorithme Tri_Selection /Version 2/ local : m, i, j, n, temp Î Entiers naturels Entrée : Tab Î.