I- Comment trier 6 cartes ?

 

Chaque nombre est placé dans une case mémoire (on dispose d'autant de cases vides que l'on veut).

Il faut obtenir une liste triée par ordre croissant. Pour pouvoir trier il faut comparer les éléments entre eux.

Quel est l'algorithme le plus rapide?

​

1) Le tri à bulle

Comparaison deux éléments côte à côte de la liste et interversion si nécessaire. Il faut pour cela l'utilisation d'une case mémoire. 

Exemple (avec l'ordre suivant): 7 13 2 26 64 52 

Au 1er tour de boucle on obtient 5 comparaisons et 6 déplacements;

Au 2nd tour de boucle on obtient 5 comparaisons et 3 déplacements;

Donc au total il y a 19 opérations.

​

2) Le tri par sélection

Le minimum de la liste est sélectionné et est placé au début. Puis dans la liste restante on sélectionne le minimum et on le place au milieu de la liste restante. Ce tri nécessite d'avoir toutes les données avant de débuter.  

​

3) Le tri par insertion

On considère que le début de la liste est déjà trié (un seul élément au début) et l'on insère l'élément suivant dans la liste à sa place dans la liste.

​

4) Le tri par fusion

On choisit de trier des sous listes de 2 éléments puis on les fusionne avec les sous listes voisines jusqu'à ce que l'ensemble de la liste sois triée.

​

II- Les fonctions sort et sorted

La fonction SORT: trie la liste en place (uniquement les listes).

La fonction SORTED: peut aussi trier les dictionnaires.

​

III- Activité du jeu de tri débranché

On dispose de 10 cartes comprenant chacune une lettre d'un côté et d'une valeur numérique de l'autre. L'enseignant répond par oui ou par non aux  comparaisons proposées par les élèves.

​

La recherche dichotomique sert lorsque l'on veut insérer un nouvel dans une liste déjà triée. On prend le milieu de cette liste et on voit si l'élément est plus petit et on le compare au milieu de la sous liste restante.

​

IV- Comparaison des tris par insertion et par sélection en Python

Pour les comparer il faut:

- pouvoir créer de grandes listes à trier,

- pouvoir mesurer le temps pour chaque tri,

- pouvoir comparer le temps d'exécution pour des tableaux de différentes tailles et pour différents algorithmes.

​

V- Automatisation de l'étude des temps d'exécuti

​