CP1 - Algo-Prog avec Python
TP8 - 2H
Énoncés d’exercices :
1. Créer une liste aléatoire d’entiers entre 0 et 20. Trier cette liste dans
l’ordre croissant en utilisant le principe du “tri par maximum”, dont voici
le principe:
a) Soit l’indice N du dernier élément du tableau, on cherche l’indice
M du maximum entre les indices 0 et N inclus, et on échange les
éléments aux indices M et N (note : à la fin de cette étape le plus
grand élément sera toujours repoussé en dernière place et n’a plus
besoin d’être considéré par la suite).
b) on répète l’étape a), mais à chaque fois on peut décrémenter N de 1
pour s’arrêter un indice plus tôt (voir la remarque entre parenthèse
dans la phase a)
2. Créer une liste aléatoire d’entiers entre 0 et 20. Trier cette liste dans l’ordre
croissant en utilisant le principe du “tri bulles” (angl. bubble sort), dont
voici le principe:
a) pour chaque indice de la liste à l’exception du dernier, si l’entier à
cet indice est strictement plus grand que le suivant, on échange les
deux (note : à la fin du parcours le plus grand élément sera toujours
repoussé en dernière place et n’a plus besoin d’être considéré par la
suite).
b) tant qu’il y a eu un échange lors de l’étape a), on répète cette étape
a), mais à chaque fois on peut s’arrêter un indice plus tôt (voir la
remarque entre parenthèse dans la phase a)
Exemple :
Passe 1
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), comparaison et donc échange des 2 premiers
éléments car 5 > 1
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), échange car 5 > 4
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), échange car 5 > 2
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), pas d’échange ici, l’ordre est bon
Passe 2
(14258)→(14258)
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), échange car 4 > 2
1
(12458)→(12458)
on ne compare pas 5 et 8 puisqu’on est dans la seconde passe, on sait que les 2
derniers sont triés. Notez que l’algorithme ne sait pas qu’en fait c’est tout le
tableau qui est trié dans cet exemple.
Passe 3
(12458)→(12458)
(12458)→(12458)
on peut arrêter ici car on est dans la passe 3 donc on sait que les 3 derniers
sont triés. Il n’y a pas eu d’échange lors de cette passe donc on peut arrêter
l’alfgorithme, on sait que tout le tableau est trié.