Remerciez-le!

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

Mr Bassem Guetif L S Mhamdia -1- LES algorithmes de tri Et de recherche A. Le t

Mr Bassem Guetif L S Mhamdia -1- LES algorithmes de tri Et de recherche A. Le tri d’un tableau : I. Introduction : Le tri est une opération qui consiste à répartir ou organiser une collection d’objets selon un ordre déterminé. Dans le domaine de l’informatique, il existe plusieurs méthodes de tri (algorithmes). Dans ce chapitre nous allons découvrir trois méthodes de tri : • Tri par sélection, • Tri à bulles, • Tri par insertion. II. Tri par sélection : Activité : Ecrire un programme qui permet de saisir un tableau T de n entiers, puis trier en ordre croissant ce tableau en utilisant la méthode de tri par sélection et afficher le résultat. a) Principe : Cette méthode de tri consiste à : 1. Se pointer à la 1ère case du tableau T et de parcourir la totalité du tableau pour repérer l’indice de la première position du minimum, 2. Comparer ce minimum avec T [1]. S’ils sont différents on les permute, 3. Le sous tableau de T allant de 2 à n est à priori non trié, on applique l’étape 1 et 2 et ainsi de suite jusqu’à l’avant dernier élément (n-1). b) Exemple : Soit un tableau T contenant les dix éléments suivants : T : 12 10 0 -5 8 12 -2 2 40 -1 1 2 3 4 5 6 7 8 9 10 Etape1 : Parcourir la totalité du tableau pour repérer le minimum (indice de la première position du minimum) et le comparer avec T [1] T : 12 10 0 -5 8 12 -2 2 40 -1 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 10 0 12 8 12 -2 2 40 -1 1 2 3 4 5 6 7 8 9 10 Le sous tableau allant de 2 à n est à priori non trié, on applique l’étape 1 et 2 et ainsi de suite jusqu’à l’avant dernier élément (n-1). Objectifs : • Manipulation des algorithmes de tri et de recherche, à savoir : Tri : par sélection, à bulles et par insertion. Recherche : séquentielle et dichotomique Indice du minimum T [1] <> T [4] alors permutation Mr Bassem Guetif L S Mhamdia -2- Etape2 : T : -5 10 0 12 8 12 -2 2 40 -1 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 -2 0 12 8 12 10 2 40 -1 1 2 3 4 5 6 7 8 9 10 Etape3 : T : -5 -2 0 12 8 12 10 2 40 -1 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 -2 -1 12 8 12 10 2 40 0 1 2 3 4 5 6 7 8 9 10 Etape4 : T : -5 -2 -1 12 8 12 10 2 40 0 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 -2 -1 0 8 12 10 2 40 12 1 2 3 4 5 6 7 8 9 10 Etape5 : T : -5 -2 -1 0 8 12 10 2 40 12 1 2 3 4 5 6 7 8 9 10 Indice du minimum T [2] <> T [7] alors permutation Indice du minimum T [3] <> T [10] alors permutation Indice du minimum T [4] <> T [10] alors permutation Indice du minimum T [5] <> T [8] alors permutation Mr Bassem Guetif L S Mhamdia -3- On obtient : T : -5 -2 -1 0 2 12 10 8 40 12 1 2 3 4 5 6 7 8 9 10 Etape6 : T : -5 -2 -1 0 2 12 10 8 40 12 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 -2 -1 0 2 8 10 12 40 12 1 2 3 4 5 6 7 8 9 10 Etape7 : T : -5 -2 -1 0 2 8 10 12 40 12 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 -2 -1 0 2 8 10 12 40 12 1 2 3 4 5 6 7 8 9 10 Etape8 : T : -5 -2 -1 0 2 8 10 12 40 12 1 2 3 4 5 6 7 8 9 10 On obtient : T : -5 -2 -1 0 2 8 10 12 40 12 1 2 3 4 5 6 7 8 9 10 Etape9 : T : -5 -2 -1 0 2 8 10 12 40 12 1 2 3 4 5 6 7 8 9 10 On obtient : Indice du minimum Indice du minimum Indice du minimum Indice du minimum T [6] <> T [8] alors permutation T [7] = T [7] alors pas de permutation T [8] = T [8] alors pas de permutation T [9] <> T [10] alors permutation Mr Bassem Guetif L S Mhamdia -4- T : -5 -2 -1 0 2 8 10 12 12 40 1 2 3 4 5 6 7 8 9 10 Remarque : • On est arrivé à l’élément numéro n-1, alors arrêt du traitement. • Nous n’avons pas besoin de traiter le dernier élément, puisque si les neuf premiers éléments sont triés alors automatiquement le dernier sera le plus grand et par conséquent il se trouve à la bonne position. c) Spécifications et algorithmes du problème : 1. Spécification du programme principale : • Résultat : Afficher le tableau T trié en utilisant une procédure Affiche • Traitements : Il faut trié le tableau T, en utilisant une procédure Tri • Données : Il faut remplir le tableau T et saisir la taille n, en utilisant la procédure Saisie 2. Algorithme du programme principal : 0) Début Tri_Selection 1) Saisie (T, N) 2) Tri (T, N) 3) Affiche (T, N) 4) Fin Tri_Selection 3. Spécification de la procédure Saisie : • Résultat : Saisir Nf et remplir Tf • Traitements : Le remplissage d’un tableau est une action répétitive, ou on connaît le nombre de répétition qui est égale à Nf, d’où utilisation de la boucle POUR … FAIRE … La saisie de l’entier Nf doit être contrôlée pour ne pas saisir un entier négatif ou supérieur à 100. Cette procédure admet deux paramètres formels qui sont Nf et Tf. 4. Algorithme de la procédure Saisie : 0) Début procédure Saisie (VAR Tf : TAB ; VAR Nf : Entier) 1) Répéter Ecrire ("Donner la taille du tableau : "), Lire (Nf) Jusqu'à (Nf dans [1..100]) 2) Pour i de 1 à Nf Faire Ecrire ("Donner l’élément N°", i, ": "), Lire (Tf[i]) Fin Pour 3) Fin Saisie 5. Spécification de la procédure Tri : • Résultat : Trier le tableau Tf • Traitements : Il s’agit d’un traitement répétitif jusqu'à l’avant dernier élément du tableau, d’où utilisation de la boucle POUR … FAIRE …, pour chaque élément nous allons exécuter deux actions : Tableau de déclaration des nouveaux types Types TAB = Tableau de 100 entiers Tableau de déclaration des Objets Objets Type/Nature T N Saisie, Affiche, Tri TAB Entier Procédure Tableau de déclaration des Objets locaux Objets Type/Nature i Entier Mr Bassem Guetif L S Mhamdia -5- Action1 : Chercher la première apparition du minimum Action2 : Comparer l’indice du minimum et celui de l’élément en cours, s’ils sont différents, alors on applique la permutation à ces deux éléments. Donc on fera appel à une fonction intitulée Premposmin qui retourne le premier indice du minimum et à une procédure intitulée Permut permettant de permuter deux éléments. Les paramètres formels pour cette procédure sont le tableau Tf et sa taille Nf. 6. Algorithme de la procédure Tri : 0) Début procédure Tri (VAR Tf : TAB ; Nf : Entier) 1) Pour i de 1 à Nf-1 Faire Pmin ← Premposmin (Tf, Nf, i) Si i ≠ Pmin Alors Permut (Tf[i], Tf[Pmin]) Finsi Fin Pour 2) Fin Tri 7. Spécification de la fonction Premposmin : • Résultat : Déterminer la première position du minimum dans un sous tableau • Traitements : Il s’agit d’un traitement répétitif jusqu'à le dernier élément du tableau, d’où utilisation de la boucle POUR … FAIRE. On doit initialiser la position du minimum à i puis faire le parcours du sous tableau, dés que on trouve un élément inférieur à ce minimum on change la position par l’indice de cet élément. Les paramètres formels de cette fonction sont Tf, Nf et pd 8. Algorithme de la fonction Premposmin : 0) Début fonction Premposmin (Tf : TAB ; Nf, pd : Entier) : Entier 1) [pm ← pd] Pour J de pd+1 à Nf Faire Si Tf[j] < Tf [pm] Alors Pm ← j Finsi Fin Pour 2) Premposmin ← pm 3) Fin Premposmin 9. Spécification de la procédure Permut : • Résultat : Permuter deux variables entiers uploads/s1/ cours-lycee-pilote-informatique-les-algorithmes-de-tri-et-de-recherche-3eme-informatique-2011-2012-mme-amira-bouganmi-pdf.pdf