21. Manipulation de liste#
Dans cette section, nous allons tenter de prendre un peu de distance avec Python et nous intéresser aux algorithmes. Un algorithme est tout simplement un ensemble d’étapes détaillées qui décrivent comment accomplir une tâche ou résoudre un problème. C’est comme un plan d’action détaillé, une idée qui doit ensuite être implémenter en Python.
Nous allons donner quelques exemple d’algorithmes pour des taches élémentaires. Nous allons ensuite en donner les implémentations en Python.
Nous commençons par des algorithmes simples pour aller faire d’autres plus avancés.
21.1. Recherche#
21.1.1. Rechercher un élément dans une séquence#
Étant donnée une séquence, comment trouver s’il existe ou non, un élément donné ? Par exemple, pour la séquence suivante, (7, 3, 5, 2, 4, 1, 8), comment déterminer si l’élément 2 est présent ?
Bien évidement, nous allons devoir déterminer algorithme que l’on pourra implémenter en Python. Cela veut dire en particulier qu’il faut se détacher du regard humain que l’on peut avoir sur le problème et qui consiste à regarder la séquence dans sa globalité et ci répondre : « bien évidemment, ça se voit ».
Une bonne approche pour cela, est d’imaginer que pour Python, une séquence est livre avec une donnée inscrite sur chaque page. On ne peut pas regarder le livre dans globablité, la seule manière de procéder est de l’analyser en parcourant les pages les unes après les autres ou accédant à une page choisie à partir de son numéro. Dans se contexte, comment, pour un livre de plusieurs miliers de pages déterminer si une donnée est présente ou non ?
Une approche que nous pourrions réaliser, serait de parcourir page après page le livre et regarder à chaque fois si la donnée recherchée est présente. Lorsqu’on trouve une telle page alors on peut répondre, « oui, le livre contient bien la donnée ». Si après avoir parcouru toutes les pages, nous n’avons pas trouvé la donnée, alors « non, le livre ne contient pas la donnée ». Cela correspond naturellement à l’algorithme de recherche d’une valeur dans une séquence.
Pour chaque valeur de la séquence
Si la valeur est celle recherchée
alors répondre oui
Répondre non
Une fois cet algorithme posé, il devient relativement direct de le convertir en Python. On peut le faire avec une boucle pour, ou avec une boucle tant que.
def rechercher(seq, elt):
for e in seq:
if e == elt:
return True
return False
rechercher( (7, 3, 5, 2, 4, 1, 8), 2)
True
rechercher( (7, 3, 5, 9, 4, 1, 8), 2)
False
Une version alternative avec la boucle tant que. Elle est un peu plus complexe car pour parcourir les valeurs de la séquence on doit gérer l’indice i à la main. On préfèrera donc la première méthode.
def rechercher(seq, elt):
i = 0
while i < len(seq):
if seq[i] == elt:
return True
else:
i += 1
return False
rechercher( (7, 3, 5, 2, 4, 1, 8), 2)
True
rechercher( (7, 3, 5, 9, 4, 1, 8), 2)
False
21.1.2. Pourquoi ne pas utiliser in ?#
Bien sur, une existe une manière plus simple de réaliser la recherche d’un élément dans une séquence. En python, c’est exactement ce que fait l’oppérateur in.
2 in (7, 3, 5, 2, 4, 1, 8)
True
2 in (7, 3, 5, 9, 4, 1, 8)
False
Pourtant cet algorithme de recherche est important, il faut être capable de le réaliser sans utiliser le mot clef in car il sera fréquent que soyez obligé de partir d’un algorithme de base et de l’adapter à vos besoins. Par exemple. Supposons que nous disposions de liste de villes suivantes.
villes = [('Paris', 48.859822979631595, 2.3424346745212903),
('Marseille', 43.3006443339931, 5.399212549333288),
('Lyon', 45.757556691319834, 4.840265609427432),
('Toulouse', 43.59682994774006, 1.4388269132731253),
('Nice', 43.706993704948886, 7.258872036700144),
('Nantes', 47.22695145891068, -1.5553965640676033),
('Montpellier', 43.61358641589052, 3.864199673082997),
('Strasbourg', 48.57698670737203, 7.749300150221324),
('Bordeaux', 44.84332596104577, -0.5809870763075933),
('Lille', 50.63004742852798, 3.0565319168675664)]
Nous souhaitons savoir s’il existe une ville de coordonnées 47.23, -1.56. Deux problèmes se posent.
Il est complexe, voir pénalisant d’utiliser l’oppérateur
in.Les coordonnées
47.23,-1.56n’existent pas dans la liste de ville. En réalité, on voit que('Nantes', 47.22695145891068, -1.5553965640676033)est un bon candidat mais avec l’oppérateurin, on ne peut pas comparer47.23avec47.22695145891068ou-1.56avec-1.5553965640676033.
Ce que nous pouvons faire par contre c’est adapter l’algorithme de recherche pour le faire fonctionner dans notre cas. Nous modifions la manière de dire quand un élément est égal à un autre. On recherche une ville dont la latitude et la longitude est à 0.1 de distance (en valeur absolue).
def rechercher_villes(villes, lat, lon):
for v in villes:
if abs(v[1]-lat) < 0.1 and abs(v[2]-lon) < 0.1:
return True
return False
rechercher_villes(villes, 47.23, -1.56)
True
21.1.3. Compter, trouver l’indice#
On peut adapter ce que l’on vient de voir pour faire des fonctions capable de compter le nombre d’occurence d’un élément ou rechercher l’indice de la première ou dernière occurence. Dans tous les cas, nous partons de l’algorithme de recherche et nous intégrons des petites modifications.
def compter_occurences(seq, elt):
nb = 0
for e in seq:
if e == elt:
nb += 1
return nb
compter_occurences( (7, 3, 2, 2, 4, 2, 8), 2)
3
def rechercher_premiere_occurence(seq, elt):
for i in range(len(seq)):
if seq[i] == elt:
return i
return None # Attention, la valeur de retour n'est pas toujours un entier
rechercher_premiere_occurence( (7, 3, 1, 2, 4, 2, 8), 2)
3
def rechercher_derniere_occurence(seq, elt):
d = None
for i in range(len(seq)):
if seq[i] == elt:
d = i
return d # Attention, la valeur de retour n'est pas toujours un entier
rechercher_derniere_occurence( (7, 3, 1, 2, 4, 2, 8), 2)
5
21.2. Rechercher un minimum#
Pour rechercher un minimum dans une séquence, on peut utiliser une variable pour stocker « la plus petite valeur » rencontrée. Ensuite, on parcours notre séquence et, pour chaque valeur, on la compare avec notre référence. Si la valeur est plus petite que la référence, on met à jour notre référence.
pt = la premiere valeur de la liste (par défaut)
pour chaque élément e de la séquence
si e < pt
alors pt = e
renvoyer pt
Ce qui donne en Python le code suivant.
def minimum(seq):
pt = seq[0]
for e in seq:
if e < pt :
pt = e
return pt
minimum((7, 3, 1, 2, 4, 2, 8))
1
Bien sur, on peut vouloir récupérer non pas la valeut du plus petit élément mais son indice dans la séquence.
def iminimum(seq):
pt = 0
for i in range(1, len(seq)): # On commence à 1 car pt vaut 0 par défaut.
if seq[i] < seq[pt] :
pt = i
return pt
iminimum((7, 3, 1, 2, 4, 2, 8))
2
En Python, il existe un raccourci pour cette oppération. Sur une séquence, on peut utiliser la fonction min (resp. max) qui renvoie la valeur du minimum (resp. maximum). Mais encore une fois, ici l’idée est de se familiariser avec ces algorithmes simples car vous allez devoir les reprendre et les adapter dans vos programmes.
21.3. Trier une liste#
Il existe un grand nombre d’algorithmes de tri. Nous commençons par un premier algorithme qui passe par la création d’une liste alternative. Ensuite nous proposerons deux algorithmes de tris dit « en place » c’est à dire qu’ils n’utilisent pas de seconde liste.
21.3.1. Créer une liste alternative#
Voici un premier algorithme qui prend en paramètre une liste l1 et crée une liste l2 avec le élément trié.
créer une nouvelle liste vide l2
tant que la liste l1 n'est pas vide
pt = rechercher l'indice de l'élément le plus petit de l1
ajouter à la fin de l2, l'élément de l1 à l'indice pt
supprimer de l1 l'élément d'indice pt
def trier(l1):
l2 = []
while len(l1)>0:
pt = iminimum(l1)
l2.append( l1[pt] )
l1.pop(pt)
return l2
trier( [7, 3, 1, 0, 4, 2, 8] )
[0, 1, 2, 3, 4, 7, 8]
Cette fonction modifie la liste donnée en paramètre. C’est pas forcément idéal.
l = [7, 3, 1, 0, 4, 2, 8]
l_ = trier(l)
l
[]
l_
[0, 1, 2, 3, 4, 7, 8]
Une première manière constite à dupliquer la liste donnée en paramètre. On ne la modifie donc pas. Il faut renvoyer la nouvelle liste triée.
def trier(l1):
l2 = []
l3 = l1[:] #copie de la liste
while len(l3)>0:
pt = iminimum(l3)
l2.append( l3[pt] )
l3.pop(pt)
return l2
l = [7, 3, 1, 0, 4, 2, 8]
l_ = trier(l)
l # n'est plus modifiée
[7, 3, 1, 0, 4, 2, 8]
l_
[0, 1, 2, 3, 4, 7, 8]
Une seconde manière de résoudre le problème consiste à remttre les éléments de la liste là où il était au début. Il est alors inutile de renvoyer une valeur puisque l’on modifie la liste passée en paramètre.
def trier(l1):
l2 = []
while len(l1)>0:
pt = iminimum(l1)
l2.append( l1[pt] )
l1.pop(pt)
for e in l2:
l1.append(e)
l = [7, 3, 1, 0, 4, 2, 8]
trier(l)
l
[0, 1, 2, 3, 4, 7, 8]
21.3.2. Tri sélection#
Une manière plus classique est le tri à sélection. Il consiste à trouver le plus petit élément d’une liste, et à l’échanger avec le premier élément, puis à répéter cette opération pour la sous-liste commençant à partir du deuxième élément. Ce tri est « en place ».
def trier(l):
for i in range(len(l)-1):
# On recherche l'élément minimum dans la sous liste l[i:] qui a l'indice i dans la liste origiinale
pt = iminimum(l[i:])+i
l[i], l[pt] = l[pt], l[i]
l = [7, 3, 1, 0, 4, 2, 8]
trier(l)
l
[0, 1, 2, 3, 4, 7, 8]
21.3.3. Tri à bulles#
Autre possiblité, le tri à bulles. Il consiste à parcourir la liste plusieurs fois en comparant les éléments adjacents et en les échangeant si nécessaire. Le nom « tri à bulles » vient du fait que les plus grandes valeurs « flottent » vers le haut de la liste comme des bulles.
def trier(l):
for _ in l:
for i in range(len(l)-1):
if l[i+1] < l[i]:
l[i], l[i+1] = l[i+1], l[i]
l = [7, 3, 1, 0, 4, 2, 8]
trier(l)
l
[0, 1, 2, 3, 4, 7, 8]
Dans le pire des cas, le nombre de fois que l’on doit faire la boucle extérieur est égale à la longueur de la liste -1. Si la liste contient peu d’inversion, on peut s’arrêter avant. On obtient alors l’algorithme la fonction suivante.
def trier(l):
b = True
while b:
b = False
for i in range(len(l)-1):
if l[i+1] < l[i]:
l[i], l[i+1] = l[i+1], l[i]
b = True
l = [7, 3, 1, 0, 4, 2, 8]
trier(l)
l
[0, 1, 2, 3, 4, 7, 8]