Devoir 2 sur les alorithmes de tri

Lis les explications au sujet des algorithmes de tri par insertion, sélection et bulles sur le site modulo-informatique: (version PDF ci-jointe).

Vous trouverez également une explication sous forme de vidéo ici.

Une fois terminé (il faut y passer du temps pour bien comprendre!), fais l'exercice 5 (dérouler le tri de la liste [2,5,3,4,7,1,6] avec une méthode de tri) et rends-le (copie chaque étape en texte avec explications) dans ce devoirs.

Voici comme exemple, le tri par bulles. Fais seulement un des deux autres algorithmes (insertion ou sélection) selon la longueur de ton prénom (dans ton identifiant EEL):

Si ton nom a un nombre de lettres impair, suis l'algorithme de tri par insertion

Si ton nom a un nombre de lettres pair, suis l'algorithme de tri par sélection

EXEMPLE:

Tri par bulles:

[2,5,3,4,7,1,6] (tirage initial)

[2,5,3,4,7,1,6] (on compare les deux premières valeurs: comme celle de droite est plus grande que celle de gauche, on ne fait rien)

[2,3,5,4,7,1,6] (on continue avec la 2ème paire: comme le nombre de droite est plus petit que celui de gauche, on les échange)

[2,3,4,5,7,1,6] (échange)

[2,3,4,5,1,7,6] (échange)

[2,3,4,5,1,6,7] (échange-> fin de la première bulle)

On recommence à partir du début pour la 2ème bulle mais on s'arrêtera à l'avant-dernire paire

pas d'échanges pour les trois premières paires...

[2,3,4,1,5,6,7] (on échange la 4ème paire)

[2,3,4,1,5,6,7] (on n'échange pas la 5ème paire)

fin de la deuxième bulle. On recommence au début pour la 3ème bulle mais on s'arrêtera à l'avant-avant-dernière paire

[2,3,1,4,5,6,7] (unique échange pendant la 3ème bulle)

[2,1,3,4,5,6,7] (unique échange pendant la 4ème bulle)

[1,2,3,4,5,6,7] (unique échange pendant la 5ème bulle)

On a fini! (15 comparaisons et 8 échanges)