Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre3: les algorithmes de tri ~ Résumé des algorithmes de tri 4ème Sciences

Chapitre3: les algorithmes de tri ~ Résumé des algorithmes de tri 4ème Sciences de l’informatique Prof. Jamel TALBI Lycée Mourouj 6 Page 1 sur 4 Tri par sélection Principe Version itérative Version récursive Le principe du tri par sélection est d'aller chercher le plus petit/grand élément du vecteur pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit/grand élément du vecteur pour le mettre en second, etc... Procedure Tri_Selection(var T:tab ; N:entier) Résultat: T_trié T: Pour i de 1 à N-1 faire ppm  FN PrePosMin(T,i,N) Si T[i] <> T [ppm] alors Proc Permut(T[i],v[ppm]) Fin Si Fin pour Fin selection Fonction PrePosMin(T :tab ; i,N:entier) :entier Résultat: PrePosMinmin Min:[mini ] Pour j de i+1 à N faire Si T[j] < T[min] alors min  j Fin Si Fin Pour Fin PrePosMin Procedure Permut (var A,B : entier) Résultat: Permuter le contenu de A et B A,B: aux  A A  B B  aux Fin Permut Procedure Tri_Selection_Rec(var T:tab; i,N:entier) Résultat: Tri_Selection_Rec Si (i < N) alors ppm  FN PrePosMin(T,i,N) Si (T[i] <> T [ppm]) alors Proc Permut(T[i],T[ppm]) Fin Si Proc Tri_Selection_Rec(T,i+1,N) Fin Si Fin Tri_Selection_Rec Fonction PrePosMin(T :tab ; i,N:entier) :entier Résultat: PrePosMinmin Min:[mini ] Pour j de i+1 à N faire Si T[j] < T[min] alors min  j Fin Si Fin Pour Fin PrePosMin Procedure permut (var A,B : entier) Résultat: Permuter le contenu de A et B A,B: aux  A A  B B  aux Fin permut NB: l'appel au niveau de programme principal se fait comme suit: Proc Tri_Selection_Rec(T,1,N) Chapitre3: les algorithmes de tri ~ Résumé des algorithmes de tri 4ème Sciences de l’informatique Prof. Jamel TALBI Lycée Mourouj 6 Page 2 sur 4 Tri à Bulles Principe Version itérative Version récursive Le principe de tri à bulle consiste à :  Parcourir le tableau en comparant deux à deux les éléments successifs, permuter s'ils ne sont pas dans l’ordre.  Répéter tant que des permutations sont effectuées. Procedure Tri_Bulles(var T :tab ; N:entier) Résultat: T_Trié T: Répéter echange  faux Pour i de 1 à N-1 faire si T[i] > T[i+1] alors echange  vrai Proc Permut(T[i], T[i+1]) fin Si Fin Pour jusqu’à Echange = faux Fin Tri_Bulles Procédure Tri_Bulles_Rec(var T:tab ; N:entier) Résultat: Tri_Bulles_Rec Si N > 1 Alors pour i de 1 à N-1 faire si T[i] > T[i+1] alors Proc Permut(T[i], T[i+1]) fin Si Fin Pour Proc Tri_Bulles_Rec(T, N-1) Fin Si Fin Tri_Bulles_Rec NB: l'appel au niveau de programme principal se fait comme suit: Proc Tri_Bulles_Rec(T,N) Tri par insertion Principe Version itérative Version récursive Le principe consiste à chercher la position de l’ième élément dans la partie du tableau commençant de 1 à i sachant que les i-1 premiers éléments sont triés. Si cette position est i, l’élément est donc à sa bonne place, sinon, supposons que cette position est j. Ce j est forcément entre 1 et i-1. On décale d’un pas vers l’avant (à droite) tous les éléments de j à i-1 puis on insère l’élément d’indice i à la position j. Procedure Tri_Insertion (var T:tab ; N:entier) Résultat: T_trié T: Pour i de 2 à N faire aux  T[i] j  i proc decaler(T,j,aux) T[j]  aux Fin pour Fin Tri_Insertion Procedure decaler(var T :tab ; var j :entier ; aux :entier) Résultat : T_décalé T_decalé : Tant que (j >1) ET (T[j-1] > aux) Faire T[j]  T[j - 1] j  j - 1 Fin Tant que Fin decaler Procedure Tri_Insertion_Rec (var vT:tab, i,N : entier) Résultat: Tri_Insertion_Rec Si (i <= N) alors aux T[i] j  i proc decaler(T,j,aux) T[j]  aux Proc Tri_Insertion_Rec(T, i+1, N) Fin Si Fin Tri_Insertion_Rec NB: l'appel au niveau de programme principal se fait comme suit: Proc Tri_Insertion_Rec(T,2,N) Chapitre3: les algorithmes de tri ~ Résumé des algorithmes de tri 4ème Sciences de l’informatique Prof. Jamel TALBI Lycée Mourouj 6 Page 3 sur 4 Tri Shell Principe Version itérative Version récursive Le principe est le suivant: Les éléments qui ne sont pas à leurs places, ne sont pas décalés de 1 à chaque fois, mais décalés d'un certain nombre de "cases". Le nombre de case de décalage est appelé le "pas". Une fois qu'on a parcouru la liste, on recommence en réduisant la taille du pas jusqu'à ce qu'il devienne 1. Quand le pas vaut 1, le tri est le même qu'un tri par insertion mais la liste est déjà presque triée grâce aux étapes précédentes. Procédure Tri_Shell (var T:tab, N: entier) Résultat: T_trié T:[p0] Tant que ( p< N) Faire p 3 * p + 1 Fin Tant que Tant que (p > 0) Faire pp div 3 Pour i de p+1 à N Faire aux  v[i] j  i proc decaler(T,j,aux,p) T[j]  aux Fin Pour Fin Tant Que Fin Tri_Shell Procedure decaler(var T :tab ; var j :entier ; aux,p :entier) Résultat : T_décalé T_decalé : Tant que (j >p) ET (T[j-p] > aux) Faire T[j]  T[j - p] j  j - p Fin Tant que Fin decaler Procédure Tri_Shell_Rec(var T :tab ; N,p: entier) Résultat: Tri_Shell_Rec Si (p>0) alors Pour i de p+1 à nb Faire aux v[i] j  i proc decaler(T,j,aux,p) T[j]  aux Fin Pour Proc Tri_Shell_Rec (T,N,p div 3) Fin Si Fin Tri_Shell_Rec Fonction Pas(N:entier):entier Résultat: Pasp p:[p0] Tant que ( p< N) Faire p 3 * p + 1 Fin Tant que Fin Pas NB: l'appel au niveau de programme principal se fait comme suit: PFN Pas(N) div 3 Proc Tri_Shell_Rec(T,N,p) Chapitre3: les algorithmes de tri ~ Résumé des algorithmes de tri 4ème Sciences de l’informatique Prof. Jamel TALBI Lycée Mourouj 6 Page 4 sur 4 Tri par fusion Principe méthode récursive Le tri par fusion utilise le principe « Diviser pour régner ». On dit que trier un tableau de taille N, c'est trier deux tableaux de taille N/2. Une fois les deux tableaux sont trié , on a plus qu'à les réunir (les fusionner) de sorte à ce que le tableau final soit trié. Ce tri utilise bien sur la notion de récursivité (un tableau étant la somme de deux tableaux) Procedure Tri_Fusion( var T :tab ; d,f :entier) Résultat : T_trié Si (d<f) alors m(d+f) div 2 Proc Tri_Fusion(T,d,m) Proc Tri_Fusion(T,m+1,f) Proc Fusionner(T,d,m,f) Fin SI Fin Tri_Fusion Procedure Fusionner(var T :tab ; d,m,f :entier) Résultat : T_Trié T : [id, jm+1] Pour k de d à f faire Si(j>f) ou ((i<=m) et( T[i]<T[j])) alors Taux[k]T[i] Ii+1 Sinon Taux[k]T[j] Jj+1 Fin si Fin pour Pour c de d à f faire T[c]Taux[c] Fin pour Fin Fusionner NB: l'appel au niveau de programme principal se fait comme suit: Proc Tri_Fusion(T,1,N) uploads/Litterature/ resume-des-algorithmes-de-tri.pdf