Remerciez-le!

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

Les différentes méthodes de tries Par Dimitri PIANETA 2015-2016 2 Table des mat

Les différentes méthodes de tries Par Dimitri PIANETA 2015-2016 2 Table des matières I)Définitions : ......................................................................................................................................3 II)Tri à Bulles (Bubble sort) : ................................................................................................................3 III)Tri par Sélection (Selection Sort) .....................................................................................................5 IV)Tri par Insertion (insertionSort) ......................................................................................................6 V)Tri par Shell (Shell sort) ....................................................................................................................7 VI)Tri rapide (Quick Sort).....................................................................................................................8 VIII)Tri par Fusion(Merge sort) ............................................................................................................9 IX) Tri par création ............................................................................................................................ 11 X) Tri trois médiane ........................................................................................................................... 13 IX) Tri par tas .................................................................................................................................... 15 3 I) Définitions : Qu’est-ce qu’un tri ? On suppose qu’on se donne une suite de N nombres entiers et on veut les ranger en ordre croissant (ou décroissant) au sens large. Ainsi, pour n=7, la suite (5, 2, 3, 0, 6, 1, 1) devra devenir (0, 1, 1, 2, 3, 5, 6). II) Tri à Bulles (Bubble sort) : Le nom de ce tri vient de ce que les éléments les plus grands (lourd) remontent vers la fin du tableau comme les bulles vers le haut d’un tube à essai. C’est le tri le plus simple. Méthode et implémentation : Le tri à bulle est une méthode de tri qui consiste à comparer successivement tous les éléments adjacents d’un tableau et à les échanger si le premier élément est supérieur au second. On recommence cette opération tant que tous les éléments ne sont pas triés. À chaque étape de l’algorithme l’élément maximal est déplacé à la fin de la suite. Voici un exemple d’application de cette méthode pour N =6 : a[0] a[1] a[2] a[3] a[4] a[5] Données 115 101 30 63 20 47 1er passage : Échanges : 101<-> 115 30 <->115 63<->115 20<->115 47<->115 Résultat du 1er passage 101 30 60 20 47 115 Au 1er passage l’élément (115), le plus grand du tableau est déplacé en N-1 (ici 5ème) position. 2ème passage : Échanges : 30<-> 101 63 <->101 20<->101 47<->101 4 Résultat du 2ème passage 30 63 20 47 101 115 Au 2ème passage l’élément (101), deuxième plus grand du tableau est déplacé en N-2 (ici 4ème) position. 3ème passage : Pas d’Échanges : 30<63 Échanges 20<->6 47<->63 Résultat du 3ème passage 30 20 47 63 101 115 Au 3ème passage l’élément (63), 3ème plus grand du tableau est déplacé en N-3 (ici 3ème) position. 4ème passage : Échanges : 20 <->30 Pas d’échange : 30<47 Résultat du 4ème passage 20 30 47 63 101 115 Au 4ème passage l’élément (47), 4ème plus grand du tableau est déplacé en N-4 (ici 2ème) position. 5ème passage : Pas d’échange : 20<30 Résultat du 5ème passage 20 30 47 63 101 115 Au 5èmele tableau est trié et l’algorithme s’arrête et on s’aperçoit qu’il y a N-1 (5 passages). 5 Pseudo code : passage ← 0 REPETER permut ← FAUX POUR i VARIANT DE 1 A n - 1 - passage FAIRE SI a[i] > a[i+1] ALORS echanger a[i] ET a[i+1] permut ← VRAI FIN SI FIN POUR passage ← passage + 1 TANT QUE permut = VRAI III) Tri par Sélection (Selection Sort) L’idée est de trier un tableau en déterminant son plus petit, con deuxième plus petit, troisième plus petit, etc. élément. C’est-à-dire trouver la position du plus petit élément dans le tableau et ensuite échanger a[0] et a[i1]. Ensuite de suite, déterminer la position i2 de l’élément avec le plus petit des a[1],…,a[N-1] et échanger a[1] et a[i2]. On continue de cette manière jusqu’à ce que tous les éléments soient dans la position correcte. Un avantage de ce tri par sélection est qu’il est progressif, car à l’étape i de l’algorithme, le tableau est trié de a[0] jusqu’à a[i-1]. a[0] a[1] a[2] a[3] a[4] a[5] Données 115 101 30 63 20 47 Sélection 20 Placement 20 101 30 63 115 47 Sélection 30 Placement 20 30 101 63 115 47 Sélection 47 Placement 20 30 47 63 115 101 Sélection 63 Placement 6 20 30 47 63 115 101 Sélection 101 Placement 20 30 47 63 101 115 Pseudo code : Pour i variant de 1 à n-1 faire Trouver[j] le plus petit element de [i+1:n] Echanger [j] et [i] IV) Tri par Insertion (insertionSort) L’idée est de trier successivement les premiers éléments du tableau. A la ième étape on insère le ième élément à son rang parmi les i-1 éléments précédents qui sont déjà triés entre eux. L’algorithme commence par s’exécuter à partir du 2ème élément du tableau. Cette méthode s’appelle aussi méthode du joueur de cartes. Les étapes successives sont décrites ci-dessous : Voici un exemple d’application pour N=6 a[0] a[1] a[2] a[3] a[4] a[5] Données 115 101 30 63 20 47 1er insertion : 101 115 30 63 20 47 2ème insertion : 30 101 115 63 20 47 3ème insertion : 30 63 101 115 20 47 4ème insertion : 20 30 63 101 115 47 5ème insertion : 20 30 47 63 101 115 7 Implémentation en java : Pseudo code : pour i variant de 2 à n faire INSERER a[i] à sa place dans a[1:i-1] V) Tri par Shell (Shell sort) Le tri Shell est une extension du tri par insertion. Exemple de tri Évolution du tableau au fil du tri shell. Le pas, représenté en rouge est également indiqué ainsi que la valeur en mémoire, sur laquelle porte la comparaison. En bleu, les valeurs sur lesquels portent les comparaisons à chaque étape. Tableau Mémoire Pas Commentaire 6 3 0 9 1 7 8 2 5 4 t(4)=1 4 Comparaison de mémoire=t(4) avec t(0) : t(4) reçoit t(0) puis t(0) reçoit mémoire 1 3 0 9 6 7 8 2 5 4 t(5)=7 4 Comparaison de mémoire=t(5) avec t(1) : pas d'échange 1 3 0 9 6 7 8 2 5 4 t(6)=8 4 Comparaison de mémoire=t(6) avec t(2) : pas d'échange 1 3 0 9 6 7 8 2 5 4 t(7)=9 4 Comparaison de mémoire=t(7) avec t(3) : t(7) reçoit t(3) puis t(3) reçoit mémoire 1 3 0 2 6 7 8 9 5 4 t(8)=5 4 Comparaison de mémoire=t(8) avec t(4) : t(8) reçoit t(4) 1 3 0 2 6 7 8 9 6 4 t(8)=5 4 Comparaison de mémoire avec t(0) : pas d'échange t(4) reçoit mémoire 1 3 0 2 5 7 8 9 6 4 t(9)=4 4 Comparaison de mémoire=t(9) avec t(5) : t(9) reçoit t(5) 1 3 0 2 5 7 8 9 6 7 4 4 Comparaison de mémoire avec t(1) : pas d'échange, t(5) reçoit mémoire 1 3 0 2 5 4 8 9 6 7 4 1 A ce stade, le pas diminue 4/3 donne un pas de 1 Implémentation en java : Pseudo-code : 1. PROCEDURE tri_Insertion ( Tableau a[1:n],gap,debut) 2. POUR i VARIANT DE debut A n AVEC UN PAS gap FAIRE 3. INSERER a[i] à sa place dans a[1:i-1]; 4. FIN PROCEDURE; 5. 6. PROCEDURE tri_shell ( Tableau a[1:n]) 8 7. POUR gap DANS (6,4,3,2,1) FAIRE 8. POUR debut VARIANT DE 0 A gap - 1 FAIRE 9. tri_Insertion(Tableau,gap,debut); 10. FIN POUR; 11. FIN POUR; 12. FIN PROCEDURE; VI) Tri rapide (Quick Sort) Principe L'algorithme de tri rapide (ou Quick Sort) a pour principe de base : on choisit une valeur dans le tableau appelée pivot (nous prendrons ici la première valeur du tableau) et on déplace avant elle toutes celles qui lui sont inférieures et après elle toutes celles qui lui sont supérieures. Puis, on réitère le procédé avec la tranche de tableau inférieure et la tranche de tableau supérieure à ce pivot. Voici un exemple : 13 18 9 15 7 Nous prenons le premier nombre en pivot : 13 et nous plaçons les nombres 9 et 7 avant le 13, les nombres 15 et 18 après le 13. 9 7 13 15 18 Il ne reste plus ensuite qu'à réitérer l'algorithme sur les deux sous-tableaux. 9 7 15 18 Le premier aura comme pivot 9 et sera réorganisé, le second aura comme pivot 15 et ne nécessitera aucune modification. Il restera alors deux sous-sous-tableaux. 7 18 Comme ces sous-sous-tableaux se résument à une seule valeur, l'algorithme s'arrêtera. Cet algorithme est donc récursif et l'une des difficultés est de répartir les valeurs de part et d'autre du nombre pivot. Revenons, à notre tableau initial. Nous allons chercher le premier nombre plus petit que 13 de gauche à droite avec une variable i, et le premier nombre plus grand que 13 de droite à gauche avec une variable j, jusqu'à ce que i et j se rencontrent. 13 18 9 15 7 On trouve 18 et 7. On les inverse et on continue. 13 7 9 15 18 Le rangement est presque fini, il ne reste plus qu'à inverser le pivot avec le 9. 9 9 7 13 15 18 Pseudo code : Tri-Rapide(A,p,r) Si p<r Alors qPARTITION(A,p,r) Tri-Rapide(A,p,q-1) Tri-Rapide(A,q+1,r) PARTITION(A,p,r) X A[r] i p-1 pour j p à r-1 faire si A[j]<= x alors ii+1 permuter A[i] A[j] permute A[i+1] A[r] retourner i+1 permute(A,I,j) memoireA[i] A[i]=A[j] A[j]=memoire VIII) Tri par Fusion(Merge sort) Le tri fusion est construit suivant la stratégie "diviser pour régner", en anglais uploads/Litterature/ les-differents-methodes-de-tries.pdf