Cours Stage - Programmation Python

Exercice - Programmation Python

L'énoncé

Répondre aux questions suivantes en utilisant le langage Python 

 


Question 1

Créer une liste L contenant les nombres 5, 4, 8, 2 dans cet ordre et l'afficher.

Pour rappel, une liste s'écrit entre crochets []. 
Pour créer une liste dont on connait les éléments, on peut simplement les énumérer. 

Le code est donc le suivante :

L = [5, 4, 8, 2]
print(L)

Une liste s'écrit entre crochets.


La fonction print() permet d'afficher des éléments. 

Question 2

Ecrire une fonction qui permet d'échanger deux éléments d'une liste. 
On pourra écrire une fonction echange(L, i, j) qui échange les éléments i et j de la liste L. 

Python permet d'échanger simplement deux éléments en utilisant la syntaxe suivante : 
x, y = y, x
Cela signifie que x prend la valeur y et y la valeur x. 

Ainsi, la fonction s'écrit :

def echange(L, i, j):
     L[i], L[j] = L[j], L[i]

L'élément d'indice i de la liste L est L[i]. 


Python permet d'échanger simplement deux éléments en utilisant la syntaxe suivante : 
x, y = y, x

Question 3

Ecrire une fonction indice_min(L, i, j) qui permet de trouver l'indice du minimum dans une liste L entre les éléments d'indices i et j, et qui retourne cet indice. 

def indice_min(L, i, j) :
     min = i #on commence par stocker l'indice i
     for x in range (i + 1, j + 1): #on partout la liste de l'indice i + 1 à j
          if L[x] < L[min] : 
               min = x #si l'élément d'indice x est plus petit que l'ancien minimum, l'indice du nouveau minimum devient x.
     return min # on retourne la valeur de l'indice de l'élément minimal

On peut commencer par stocker dans une variable min l'indice i. 


On parcourt ensuite la liste entre i + 1 et j, à l'aide d'une boucle for.


Dès qu'un élément est plus petit que le minimum qu'on avait jusqu'alors, on met à jour l'indice du minimum. 


La fonction range(i, j) parcourt les entiers de i à j - 1. 

Question 4

Le principe de l'algorithme est le suivant :
On parcourt d'abord toute la liste pour trouver l'indice du minimum puis on échange le premier élément de la liste avec cet élément minimal.
On parcourt ensuite la liste en partant du second indice pour trouver le nouveau minimum de cette sous-liste que l'on échange ensuite avec le second élément de la liste.
Puis on continue jusqu'à avoir parcouru toute la liste.

Ecrire les différentes étapes du tri de la liste L en suivant le même principe que l'algorithme précédent.

On écrit la liste pendant les différentes étapes du tri :
L = [5, 4, 8, 2]
L'élément minimal en parcourant la liste entière est 2.
On échange donc 5 et 2.
L = [2, 4, 8, 5]
On cherche ensuite le minimum de la sous liste comprise entre les indices 1 et 3 : c'est 4, qui est déjà à la bonne place.
L = [2, 4, 8, 5]
On cherche ensuite le minimum de la sous liste comprise entre les indices 2 et 3 : c'est 5, on échange donc 8 et 5. 
L = [2, 4, 5, 8]

 

Commencer par chercher le minimum de la liste. 


Echanger le premier élément de la liste avec le minimum, puis recommencer à chercher le minimum de la sous liste entre les indices 1 et 3. 

Question 5

Ecrire une fonction tri(L) qui trie la liste L en utilisant les deux fonctions précédentes.

 Le principe de l'algorithme est le suivant :
On parcourt d'abord toute la liste pour trouver l'indice du minimum puis on échange le premier élément de la liste avec cet élément minimal.
On parcourt ensuite la liste en partant du second indice pour trouver le nouveau minimum de cette sous-liste que l'on échange ensuite avec le second élément de la liste.
Puis on continue jusqu'à avoir parcouru toute la liste.

def tri(L):
    n = len(L) #on stocke dans n la longueur de la liste L
    for i in range(n - 1) # on ne regardera pas le dernier élément à la toute fin car cela sera nécessairement le plus grand
         i_min = indice_min(L, i, n - 1) #on trouve l'indice du minimum pour la liste comprise entre les indices i et n - 1.
         echange(L, i, i_min) #on échange les éléments d'indices i et i_min

 

On pourra utiliser une boucle for

Question 6

Cet algorithme vous semble-t-il optimal ? 

Concernant l'optimalité de l'algorithme de tri, on remarque que l'on utilise tout d'abord une boucle dans la fonction tri, et la fonction tri fait également appel à une boucle. 
Lors du premier passage dans la boule de la fonction tri, on effectue n - 1 comparaisons. 
Lors du second passage, on effectue n - 2 comparaisons.
Ainsi, la boucle de la fonction tri est de longueur n - 2, on aura effectué n - 2 + n - 3 + ... + 2 + 1 comparaisons, c'est à dire $\dfrac{(n - 2) \times (n - 1)}{2}$ comparaisons, si $n$ est grand cela vaut environ $n^2$. 
Si la liste était triée dans le sens décroissant, on aurait donc stocké environ $n^2$ fois un indice du minimum, ce qui est beaucoup, car ce dernier aurait changé à chaque comparaison comme l'élément de gauche étant forcément plus grand que celui qui le suit. 

Ainsi, l'algorithme n'est pas optimal.

Cet algorithme est appelé tri par sélection. 

Compter grossièrement le nombre de comparaisons/affectation que l'on effectue.


On pourra raisonner avec une liste triée dans l'ordre décroissant. Que se passe-t-il ?