Tri Par Extraction Dents
/**sous programme codant le tri par la methode tri par bulles void triBulle ( Tableau T, int nb) printf ( "Tri par Bulles, initialement T = "); for ( i = 0; i < nb; i ++) for ( j = 0; j < nb - 1; j ++) if ( T [ j] > T [ j + 1]) permuter ( T, j, j + 1);}}} printf ( "fin du tri par Bulles, nb comparaisons =%d, nb permutations =%d. \n ", nbComp, nbPermut); printf ( "Tri par Bulles, maintenant T = "); Le tri par extraction est plus économe en termes de permutations. Au premier tour de tri, l'élément le plus grand du tableau à trier est recherché, puis il est échangé avec la dernière valeur du tableau (si besoin) Au second tour de tri, il y a recherche du second élément le plus grand qui est placé à l'avant dernière place, etc... on prend 10 et on cherche dans les précédents la plus grande valeur supérieure à 10 aucune n'est trouvée, le tableau reste identique. au tour suivant, on prend 5 et on cherche dans les précédents la plus grande valeur supérieure à 5. 9 est trouvé, les places sont échangées: T = [8, 6, 5, 9, 10] au tour suivant, on prend 5 et on cherche dans les précédents la plus grande valeur supérieure à 5.
Tri Par Extractions
En résumé, lorsque on utilise le tri par sélection: On effectue environ \frac{n(n-1)}{2} comparaisons; On effectue environ n échanges; La complexité moyenne et dans le pire des cas est quadratique.
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 i+1 jusquà n faire " la variable m contient l'indice
de min( a i+1, a k+2,..., 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/
a i = Tab[ i]
pour j de i+1 jusquà n faire // ( a i+1,
a 2,..., a n)
j; // indice mémorisé
fpour;
Tab[ m] ¬ Tab[ i];
Tab[ i] ¬ temp //on échange les positions de a i et de a j
D) Complexité:
Choisissons comme opération élémentaire
la comparaison de deux cellules
du tableau. 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 " pour i de
1 jusquà n-1 faire "
s'exécute n-1 fois (donc une somme de n-1 termes) et qu'à chaque
fois la boucle " pour j de i+1
jusquà n faire " exécute (n-(i+1)+1 fois la comparaison
" si Tab[ j] < Tab[ m] alors ".