NSI : listes et algorithmes de tris

1. Listes en Python

A. Découverte des listes

Contrairement aux tuples, les listes en pythons sont des listes d’objets dont on peut modifier les valeurs.
Pour les découvrir, nous allons utiliser pythonDoctor qui permet de mieux comprendre certaines spécificités des listes et surtout la notion d’égalité entre listes.

http://www.pythontutor.com/live.html#mode=edit

On déclare une liste en Python à l’aide de crochets.
Tester les commandes suivantes dans l’éditeur de code pythontutor:

a=[1,2,"a"]
print(a[1])
print(len(a))
a.append(5)
a[0]=0

B. Liste définie par compréhension

On peut définir une liste par compréhension.

a=[i for i in range(10)]

Exercice 1

  1. On considère les listes ci-dessous définies en extension :
>>> a=[0,2,4,6,8,10]
>>> b=[0,1,4,9,16,25,36]
>>> c=[10,9,8,7,6,5,4,3,2]

Déterminer comment les définir par compréhension.

2. Que retournent les commandes ci-dessous ?

>>>[i+j for i in [3,1,2] for j in [2,1]]
>>>[i+j for j in [1,3] for i in [1,0,2] ]
>>>[[i+j for i in range(3)] for j in range(2)]

3. Notion de pointeurs et usage délicats des listes

Taper les commandes suivantes

>>> a=5
>>> b=a
>>> print(a)
>>> print(b)
>>> a=7
>>> print(a)
>>> print(b)

Taper à présent les commandes suivantes :

>>> a=[2,3]
>>> b=a
>>> print(a)
>>> print(b)
>>>a[0]=5
>>> print(a)
>>> print(b)
>>>b[1]=12
>>> print(a)
>>> print(b)

Une différence singulière apparait entre les commandes d’affectation entre des variables de type int et des listes.
Analyser les différences avec Pythontutor
La méthode copy() permet de lever certains de ces problèmes.
Analyser la différence avec pythontutor :

>>> a=[2,3]
>>> b=a.copy()
>>> print(a)
>>> print(b)
>>>a[0]=5
>>> print(a)
>>> print(b)
>>>b[1]=12
>>> print(a)
>>> print(b)

4. Exercices

Exercice 2

Ecrire une fonction permettant de remplir aléatoirement un liste de longueur n par des nombres entiers compris entre 0 et 100.
La fonction utilisera une liste en compréhension et la méthode randint() du module random.

>>> # par exemple
>>> liste_aleatoire(5)
>>> [6,19,54,27,4]
# proposition correction
from random import randint

def liste_aleatoire(n):
    # générer aléatoirement un liste de taille n
    # contenant des nbres entiers entre 0 et 100
    return [randint(0,100) for i in range(n)]

Exercice 3

Ecrire une fonction inverse retournant la liste inversée d’un liste passée en paramètre.

>>> # par exemple
>>> a=[1,7]
>>> inverse_liste(a)
>>> [7,1]
# proposition correction def inverse_liste(a): # inverse les termes de la liste retour=[] for i in range(len(a)): retour.append(a[len(a)-1-i]) return retour

Exercice 4

Ecrire une fonction triee() permettant de déterminer si une liste est triée par ordre croissant

>>> a=[7,3,6]
>>> triee(a)
False
>>> b=[5,8,15]
>>> triee(b)
True
# correction
def triee(a):
    # indique si une liste est triée
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True

2. Méthodes de tris

Pour pouvoir étudier des données, il est souvent nécessaire de les trier par ordre croissant ou décroissant.
Il existe différentes méthodes pour cela.
Ces algorithmes diffèrent par leurs complexités et leurs efficacités.
Pour visualiser différents algorithmes de tri :
https://www.toptal.com/developers/sorting-algorithms

A. permuter le contenu de deux variables

Il est souvent nécessaire en informatique et plus particulièrement sur les algorithmes de tris de permuter le contenu de deux variables.
Pour cela, on a souvent besoin d’utiliser une troisième variable temporaire

>>> a=5
>>> b=8
>>> a=b
>>> a
8
>>> b
8
>>> a=5
>>> b=8
>>> temp=a
>>> a=b
>>> b=temp
>>> a
8
>>> b
5
# en python, il n'est pas nécessaire d'utiliser cette variable intermédiaire, on peut avoir recours à une affectation par tuple
>>> a=5
>>> b=8
>>> a,b=b,a
>>> a
8
>>> b
5
>>> a=[1,3,7,4]
>>> a[0],a[3]=a[3],a[0]
>>> a
[4,3,7,1]

B. Tri par sélection

Exercice 5

Après avoir lu la partie de l’article sur les algorithmes de tris de la revue Interstice sur le tri par sélection, écrire une fonction tri_selection() permettant de ranger par ordre croissant une liste passée en paramètre en utilisant cette méthode.

>>> # par exemple
>>> a=[7,2,1,6]
>>> tri_selection(a)
>>> [1,2,6,7]

Exercice 6

Ecrire une fonction ordre_decroissant_liste(a) permettant de ranger par ordre décroissant une liste passée en paramètre.
Cette fonction pourra utiliser les deux fonctions précédentes.

>>> # par exemple
>>> a=[7,2,1,6]
>>> ordre_decroissant_liste(a)
>>> [7,6,2,1]

C. Tri par propagation ou tri bulle.

Exercice 7

Après avoir lu la partie de l’article sur les algorithmes de tris de la revue Interstice sur le tri bulle, écrire une fonction tri_bulle() permettant de ranger par ordre croissant une liste passée en paramètre en utilisant cette méthode.

>>> # par exemple
>>> a=[7,2,1,6]
>>> tri_bulle(a)
>>> [1,2,6,7]