Algorithme Flashcards
Lorsqu’on ne trie pas les données, quel est la relation qu’on peut conclure entre le temps et la taille d’un tableau ?
Quand on double la longueur du tableau, on double le temps de recherche. Le temps croît linéairement avec la taille du tableau.
Quel est le problème si on ne trie pas les données ?
Lorsque les données ne sont pas triées, on doit chercher un élément à la fois et on ne sait même pas si on va trouver ce dont on a de besoin sans lire d’abord chaque élément du jeu de données.
Vrai ou faux ? Chercher un élément dans un tableau trié se fait efficacement ?
Vrai, cela se fait efficacement avec une recherche binaire/dichotomique.
Explique le concept de recherche dichotomique
Diviser le tableau en la moitié qui pourrait contenir l’élément , et ce jusqu’à ce que le nombre d’emplacements possibles est réduit à un seul.
Lorsqu’on trie les données, quel est la relation qu’on peut conclure entre le temps et la taille d’un tableau ?
Quand on quadruple la longueur du tableau, on double (même pas) le temps de recherche. Le temps croît logarithmiquement avec la taille du tableau.
Nomme trois méthodes de tri classiques
le tri par sélection, le tri par insertion et le tri par bulles
Qu’est-ce que le tri par sélection ?
On sélectionne le plus petit, on l’insère au début, on rapplique sur la liste moins le premier
Qu’est-ce que le tri par insertion ?
On prend les éléments un à un et on les insère à la bonne place à partir du début
Qu’est-ce que le tri par bulles
On regarde les éléments par paires en échangeant leurs positions s’ils ne sont pas dans le bon ordre. Cela fait monter le plus grand élément jusqu’au bout. Une fois le plus grand placé, on répète sur les autres éléments à partir du début.
Ça prend combien de temps pour trier ?
n comparaison pour n éléments. Donc n carrée comparaisons en tout.
Si on a un ensemble de 128 éléments, en pire cas, on a 128 comparaisons à faire pour chaque éléments. Si on a n = 128 éléments, au pire des cas on pourra trier avec 16384 comparaisons.
Quel est le moyen pour rendre plus rapide le tri ?
diviser le tri en deux listes, les trier et les fusionner en une seul liste triée.
Donc si on a 128 éléments, au pire des cas on les tries en 16384 comparaisons, ou on trie les 2 moitiés avec 4096 comparaisons chacune + 128 comparaisons pour les fusionner, ce qui donne 8320 comparaisons au total !
L’idée de diviser pour régner a donné naissance à quoi ?
Cela a donné naissance à plusieurs méthodes de tri dont le nombre de comparaisons suit une progression de nlog2n plutôt que n au carrée, e qui est un gain considérable. Pour 128 éléments on parle de, en pire cas, 128 x 7 = 896 comparaisons, plutôt que 16384.
Défini le tri par fusion
C’est un algorithme de comparaison qui prend une liste et qui divise la liste jusqu’à temps qu’il y a un élément. Par la suite, cette liste va être comparée à la liste voisine afin de les trier selon leur ordre de croissance et des les fusionner. Au final, tous les éléments seront triés et fusionnées.
Défini le tri rapide
La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui sont supérieurs au pivot soient à sa droite.
Défini le tri par monceau
La méthode consiste a crée un arbre binaire dont le premier élément sera au sommet de l’arbre. Par la suite, après avoir complété l’arbre binaire, on remplace le premier élément au top de l’arbre par l’élément le plus grand et on trie en ordre croissant dans la branche de l’arbre impliqué dans ce remplacement. Par la suite, on remplace l’élément au sommet par le dernier élément et on le supprime de l’arbre binaire. En faisant cela, le numéro le plus grand se retrouvera dans le dernier index, et on continue comme ça jusqu’à temps que le tout soit trié.
