Cours 4 - Tris & fouilles

Question 1

Quelle est la stratégie de tris la moins couteuse en terme d’espace mémoire?

Answer 1

Trier les données en interchangeant les éléments dans la structure.

Question 2

Quelles sont les trois algorithme de tris vu en classe?

Answer 2

Tri par séléction
Tri par insertion
Tri à bulle

Question 3

Tri par sélection ?

Answer 3

1 On selectionne le plus petit élément.
2 On l’échange avec le premier.
3 On recommence jusqu’à la fin du tableau.

Question 4

Tri par insertion ?

Answer 4

Prémisse : le 1er élément est trié

2 On insère tout les éléments restants à gauche de ceux précédemment trié.

Question 5

Tri à bulle?

Answer 5

On parcourt à partir de la fin (deux case à la fois).

1 Si l’élément de droite est plus petit que celui de gauche, on les échange.

Question 6

La meilleur fouille?

Answer 6

Fouille Binaire

Question 7

Fouille biniare quoi?

Answer 7

Premisse : tab déjà trié.
debut = 1
fin = nbEle
while (ele pas trouvé && fin > début) {
millieu = (debut + fin) / 2
Si ele = tab[millieu] alors c’est fini
Sinon
Si tab[millieu] > ele alors fin = millieu - 1
Si tab[millieu] < ele alors fin = début + 1