CM07 Tris lents

Télécharger le CM07 Tris lents en pdf

Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

Page 1 : Informatique IITris lents

Page 2 : Trier un tableaux27 63 1 72 64 58 14 91 9 14 27 58 63 64 72⚫Un algorithme de tri permet de modifier un tableau afin de ranger ses éléments dans l’ordre croissant ou décroissant.⚫Permet de faciliter la recherche dichotomie possible.

Page 3 : Trier un tableaux⚫Problème très classique en algorithmie!https://fr.wikipedia.org/wiki/Algorithmedetri

Page 4 : 3 algorithmes de tri « lents »⚫Tri par sélection⚫Tri à bulles ⚫Tri par insertion

Page 5 : Tri par sélection ⚫Exemple27 63 1 72 64 58 14 9⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 6 : Tri par sélection ⚫Exemple27 63 1 72 64 58 14 9⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 7 : Tri par sélection ⚫Exemple1 63 27 72 64 58 14 9⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 8 : Tri par sélection ⚫Exemple1 63 27 72 64 58 14 9⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 9 : Tri par sélection ⚫Exemple1 9 27 72 64 58 14 63⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 10 : Tri par sélection ⚫Exemple1 9 27 72 64 58 14 63⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 11 : Tri par sélection ⚫Exemple1 9 14 72 64 58 27 63⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 12 : Tri par sélection ⚫Exemple1 9 14 27 64 58 72 63⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 13 : Tri par sélection ⚫Exemple1 9 14 27 58 64 72 63⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 14 : Tri par sélection ⚫Exemple1 9 14 27 58 63 72 64⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau

Page 15 : Tri par sélection ⚫Principe⚫Rechercher le plus petit élément et le placer à l’indice 0⚫Rechercher le second plus petit élément et le placer à l’indice 1⚫Continuer jusqu’à avoir trié tout le tableau⚫Exemple1 9 14 27 58 63 64 72

Page 16 : Tri par sélection ⚫AlgorithmePROCEDURE TriSelectionAn :Tableau T de taille nVARIABLEnoEtape, noCase, indiceMin : ENTIERtemp : TDEBUTPOUR noEtape de 0 à n-1 FAIREindiceMin ← noEtapePOUR noCase de noEtape + 1 à n FAIRESI AnoCase AindiceMin ALORSindiceMin ← noCaseFIN SIFIN POURSI indiceMin noEtape Alorstemp ← AindiceMinAindiceMin ← AnoEtapeAnoEtape ← tempFIN SIFIN POURFIN

Page 17 : Tri par sélection ⚫AlgorithmePROCEDURE TriSelectionAn :Tableau T de taille nVARIABLEnoEtape, noCase, indiceMin : ENTIERtemp : TDEBUTPOUR noEtape de 0 à n-1 FAIREindiceMin ← noEtapePOUR noCase de noEtape + 1 à n FAIRESI AnoCase AindiceMin ALORSindiceMin ← noCaseFIN SIFIN POURSI indiceMin noEtape Alorstemp ← AindiceMinAindiceMin ← AnoEtapeAnoEtape ← tempFIN SIFIN POURFINT: type quelconque

Page 18 : Tri par sélection ⚫AlgorithmePROCEDURE TriSelectionAn :Tableau T de taille nVARIABLEnoEtape, noCase, indiceMin : ENTIERtemp : TDEBUTPOUR noEtape de 0 à n-1 FAIREindiceMin ← noEtapePOUR noCase de noEtape + 1 à n FAIRESI AnoCase AindiceMin ALORSindiceMin ← noCaseFIN SIFIN POURSI indiceMin noEtape Alorstemp ← AindiceMinAindiceMin ← AnoEtapeAnoEtape ← tempFIN SIFIN POURFINRecherche n fois du minimum dans le tableau

Page 19 : Tri par sélection ⚫AlgorithmePROCEDURE TriSelectionAn :Tableau T de taille nVARIABLEnoEtape, noCase, indiceMin : ENTIERtemp : TDEBUTPOUR noEtape de 0 à n-1 FAIREindiceMin ← noEtapePOUR noCase de noEtape + 1 à n FAIRESI AnoCase AindiceMin ALORSindiceMin ← noCaseFIN SIFIN POURSI indiceMin noEtape Alorstemp ← AindiceMinAindiceMin ← AnoEtapeAnoEtape ← tempFIN SIFIN POURFINRecherche du minimum dans le sous-tableau

Page 20 : Tri par sélection ⚫AlgorithmePROCEDURE TriSelectionAn :Tableau T de taille nVARIABLEnoEtape, noCase, indiceMin : ENTIERtemp : TDEBUTPOUR noEtape de 0 à n-1 FAIREindiceMin ← noEtapePOUR noCase de noEtape + 1 à n FAIRESI AnoCase AindiceMin ALORSindiceMin ← noCaseFIN SIFIN POURSI indiceMin noEtape Alorstemp ← AindiceMinAindiceMin ← AnoEtapeAnoEtape ← tempFIN SIFIN POURFINEchange des cases du tableau

Page 21 : Tri par sélection : complexité ⚫Meilleur cas :⚫Nombre de comparaisons : ⚫Nombre d’échanges :

Page 22 : Tri par sélection : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : 0

Page 23 : Tri par sélection : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : 0Complexité : On²

Page 24 : Tri par sélection : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : 0Complexité : On²⚫Pire cas⚫Nombre de comparaisons : ⚫Nombre d’échanges :

Page 25 : Tri par sélection : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : 0Complexité : On²⚫Pire cas le tableau est de la forme 5 1 2 3 4 :⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : n-1

Page 26 : Tri par sélection : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : 0Complexité : On²⚫Pire cas le tableau est de la forme 5 1 2 3 4 :⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : n-1Complexité : On²

Page 27 : Tri par sélection : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : 0Complexité : On²⚫Pire cas le tableau est de la forme 5 1 2 3 4 :⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : n-1Complexité : On²⚫Cas moyen : On²

Page 28 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 63 1 72 64 58 14 9

Page 29 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 63 1 72 64 58 14 9

Page 30 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 63 1 72 64 58 14 9On échange !

Page 31 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 72 64 58 14 9

Page 32 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 72 64 58 14 9

Page 33 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 72 64 58 14 9

Page 34 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 72 58 14 9

Page 35 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 72 58 14 9

Page 36 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 58 72 14 9

Page 37 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 58 72 14 9

Page 38 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 58 14 72 9

Page 39 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 58 14 72 9

Page 40 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 58 14 9 72

Page 41 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple27 1 63 64 58 14 9 72On recommence!

Page 42 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 64 58 14 9 72On recommence!

Page 43 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 64 58 14 9 72On recommence!

Page 44 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 64 58 14 9 72On recommence!

Page 45 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 64 58 14 9 72On recommence!

Page 46 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 64 14 9 72On recommence!

Page 47 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 64 14 9 72On recommence!

Page 48 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 64 9 72On recommence!

Page 49 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 64 9 72On recommence!

Page 50 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 9 64 72On recommence!

Page 51 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 9 64 72Pas besoin de tester la dernière case: la plus grande valeur est forcément à la fin!

Page 52 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 9 64 72

Page 53 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 9 64 72

Page 54 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 63 58 14 9 64 72

Page 55 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 63 14 9 64 72

Page 56 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 63 14 9 64 72

Page 57 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 14 63 9 64 72

Page 58 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 14 63 9 64 72

Page 59 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 14 9 63 64 72

Page 60 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 14 9 63 64 72

Page 61 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 14 9 63 64 72

Page 62 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 58 14 9 63 64 72

Page 63 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 14 58 9 63 64 72

Page 64 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 14 58 9 63 64 72

Page 65 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 14 9 58 63 64 72

Page 66 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 14 9 58 63 64 72

Page 67 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 27 14 9 58 63 64 72

Page 68 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 14 27 9 58 63 64 72

Page 69 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 14 27 9 58 63 64 72

Page 70 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 14 9 27 58 63 64 72

Page 71 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 14 9 27 58 63 64 72

Page 72 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 14 9 27 58 63 64 72

Page 73 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 9 14 27 58 63 64 72

Page 74 : Tri à bulle⚫Principe⚫On compare les éléments deux à deux ⚫Comparer chaque élément avec l’élément suivant et les permuter si besoin⚫Recommencer jusqu’à ce qu’il n’y ait plus d’échange à faire⚫Exemple1 9 14 27 58 63 64 72

Page 75 : Tri à bulle⚫AlgorithmePROCEDURE TriBulleAn :Tableau de Tdesordre : BOOLEENnoEtape, noCase : ENTIERtemp : TDEBUTnoEtape ←n - 1Fairedesordre ←FAUXPour noCase de 0 à noEtape FaireSi AnoCase AnoCase + 1 Alorsdesordre ←VRAItemp ←AnoCaseAnoCase ←AnoCase + 1 AnoCase + 1 ←tempFinSiFinPournoEtape ←noEtape - 1TantQue noEtape 0 et desordreFin

Page 76 : Tri à bulle⚫AlgorithmePROCEDURE TriBulleAn :Tableau de Tdesordre : BOOLEENnoEtape, noCase : ENTIERtemp : TDEBUTnoEtape ←n - 1Fairedesordre ←FAUXPour noCase de 0 à noEtape FaireSi AnoCase AnoCase + 1 Alorsdesordre ←VRAItemp ←AnoCaseAnoCase ←AnoCase + 1 AnoCase + 1 ←tempFinSiFinPournoEtape ←noEtape - 1TantQue noEtape 0 et desordreFinComparaison et échange de cases voisines

Page 77 : Tri à bulle⚫AlgorithmePROCEDURE TriBulleAn :Tableau de Tdesordre : BOOLEENnoEtape, noCase : ENTIERtemp : TDEBUTnoEtape ←n - 1Fairedesordre ←FAUXPour noCase de 0 à noEtape FaireSi AnoCase AnoCase + 1 Alorsdesordre ←VRAItemp ←AnoCaseAnoCase ←AnoCase + 1 AnoCase + 1 ←tempFinSiFinPournoEtape ←noEtape - 1TantQue noEtape 0 et desordreFinParcours du tableau

Page 78 : Tri à bulle⚫AlgorithmePROCEDURE TriBulleAn :Tableau de Tdesordre : BOOLEENnoEtape, noCase : ENTIERtemp : TDEBUTnoEtape ←n-1Fairedesordre ←FAUXPour noCase de 0 à noEtape FaireSi AnoCase AnoCase + 1 Alorsdesordre ←VRAItemp ←AnoCaseAnoCase ←AnoCase + 1 AnoCase + 1 ←tempFinSiFinPournoEtape ←noEtape - 1TantQue noEtape 0 et desordreFinRecommencer tant que le tableau n’est pas trié

Page 79 : Tri à bulle : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : ⚫Nombre d’échanges : Complexité : On

Page 80 : Tri à bulle : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On

Page 81 : Tri à bulle : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On⚫Pire cas ⚫Nombre de comparaisons : ⚫Nombre d’échanges :

Page 82 : Tri à bulle : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On⚫Pire cas le tableau est trié dans l’ordre inverse5,4,3,2,1⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : n-1+n-2+…+1 = nn-1/2Complexité : On²

Page 83 : Tri à bulle : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On⚫Pire cas le tableau est trié dans l’ordre inverse⚫Nombre de comparaisons : n-1+n-2+…+1 = nn-1/2⚫Nombre d’échanges : n-1+n-2+…+1 = nn-1/2Complexité : On²⚫Cas moyen : On²

Page 84 : Tri par insertion⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion⚫Exemple27 63 1 72 64 58 14 9Pas d’element precedent

Page 85 : Tri par insertion⚫Exemple27 63 1 72 64 58 14 9On passe à l’element suivant et on le compare à ses éléments precedents⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 86 : Tri par insertion⚫Exemple27 63 1 72 64 58 14 9L’élément est déjà bien placé, on passe au suivant.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 87 : Tri par insertion⚫Exemple1 27 63 72 64 58 14 9On place l’element là où il faut par rapport à seséléments précédents⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 88 : Tri par insertion⚫Exemple1 27 63 72 64 58 14 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 89 : Tri par insertion⚫Exemple1 27 63 72 64 58 14 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 90 : Tri par insertion⚫Exemple1 27 63 64 72 58 14 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 91 : Tri par insertion⚫Exemple1 27 63 64 72 58 14 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 92 : Tri par insertion⚫Exemple1 27 58 63 64 72 14 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 93 : Tri par insertion⚫Exemple1 27 58 63 64 72 14 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 94 : Tri par insertion⚫Exemple1 14 27 58 63 64 72 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 95 : Tri par insertion⚫Exemple1 14 27 58 63 64 72 9On parcourt ainsi tous les éléments.⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion

Page 96 : Tri par insertion⚫Principe⚫Prendre les éléments dans l’ordre et comparer chaque élément avec les éléments précédents du tableau pour déterminer son emplacement⚫Décaler les éléments du tableau pour faire l’insertion⚫Exemple1 9 14 27 58 63 64 72On parcourt ainsi tous les éléments.

Page 97 : Tri par insertion⚫AlgorithmePROCEDURE TriInsertionAn :Tableau de TVariablesnoetape, decalage :ENTIERtemp : TDEBUTPOUR noetape de 1 à n FAIREtmp ←Anoetapedecalage ←noetape -1TANT QUE decalage = 0 et Adecalage tmp FAIREAdecalage + 1 ←Adecalagedecalage ←decalage - 1FIN TANT QUEAdecalage + 1 ←tmpFIN POURFIN

Page 98 : Tri par insertion⚫AlgorithmePROCEDURE TriInsertionAn :Tableau de TVariablesnoetape, decalage :ENTIERtemp : TDEBUTPOUR noetape de 1 à n FAIREtmp ←Anoetapedecalage ←noetape -1TANT QUE decalage = 0 et Adecalage tmp FAIREAdecalage + 1 ←Adecalagedecalage ←decalage - 1FIN TANT QUEAdecalage + 1 ←tmpFIN POURFINGestion de l’element à traiter

Page 99 : Tri par insertion⚫AlgorithmePROCEDURE TriInsertionAn :Tableau de TVariablesnoetape, decalage :ENTIERtemp : TDEBUTPOUR noetape de 1 à n FAIREtmp ←Anoetapedecalage ←noetape -1TANT QUE decalage = 0 et Adecalage tmp FAIREAdecalage + 1 ←Adecalagedecalage ←decalage - 1FIN TANT QUEAdecalage + 1 ←tmpFIN POURFINDécalage des éléments du tableauavant placement

Page 100 : Tri par insertion⚫AlgorithmePROCEDURE TriInsertionAn :Tableau de TVariablesnoetape, decalage :ENTIERtemp : TDEBUTPOUR noetape de 1 à n FAIREtmp ←Anoetapedecalage ←noetape -1TANT QUE decalage = 0 et Adecalage tmp FAIREAdecalage + 1 ←Adecalagedecalage ←decalage - 1FIN TANT QUEAdecalage + 1 ←tmpFIN POURFINPlacement de l’élément à la bonne place

Page 101 : Tri par insertion : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : ⚫Nombre d’échanges : Complexité :

Page 102 : Tri par insertion : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On

Page 103 : Tri par insertion : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On⚫Pire cas ⚫Nombre de comparaisons : ⚫Nombre d’échanges :Complexité :

Page 104 : Tri par insertion : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On⚫Pire cas le tableau est trié dans l’ordre inverse⚫Nombre de comparaisons : On²⚫Nombre d’échanges : On²Complexité : On²

Page 105 : Tri par insertion : complexité ⚫Meilleur cas tableau déjà trié:⚫Nombre de comparaisons : n-1⚫Nombre d’échanges : 0Complexité : On⚫Pire cas le tableau est trié dans l’ordre inverse⚫Nombre de comparaisons : On²⚫Nombre d’échanges : On²Complexité : On²⚫Cas moyen : On²

Page 106 : Comparaison des tris lents

Page 107 : Trier un tableaux⚫Autres tris :https://fr.wikipedia.org/wiki/Algorithmedetri

Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107