Traitement des listes en Python

La question du tri

Dans le traitement de l'information, la notion de tri des données intervient très fréquemment.

De nombreuses méthodes de tri ont été mises au point, certaines plus efficaces que d'autres, certaines plus complexes que d'autres. Nous allons aborder ici une méthode possible: le tri pas sélection. Avantage: cette méthode est simple à comprendre. Inconvénient: elle n'est pas très efficace sur des données volumineuses.

Nous utiliserons ici le langage Python en version 3. La notion de tri sera appliquée sur les listes.

Informations préliminaires

Désigner un élément d'une liste (rappel)

Pour réaliser un tri sur une liste, nous aurons besoin de quelques outils.

Soit la liste liste = [19,72,43,17,45,42,14,2,27,56]

Désigner un élément d'une liste par son numéro d'ordre

liste[0]

désigne le premier élément (soit 19, ici)

n = 4
liste[n]

désigne le nombre "45" dont l'indice dans la liste est 4 (en commençant par 0)

liste[n+1]

désigne le nombre "42" dont l'indice dans la liste est 4+1 = 5

La longueur d'une liste

print(len(liste))

"len" est l'abréviation du mot "length". L'instruction donne le nombre d'éléments dans la liste

Quel résultat renvoie l'instruction si elle est appliquée à notre liste définie ci-dessus?

Permuter deux éléments d'une liste

Comme pour la permutation de deux variables, la permutation de deux éléments d'une liste exige l'utilisation d'une variable supplémentaire temporaire

Il serait pratique de disposer d'une fonction qui permettra la permutation.

def permuter (liste, i, j):
...intermediaire = liste[i]
...liste[i] = liste[j]
...liste[j] = intermediaire

Quelle sera l'instruction qui permettra de permuter le premier et le dernier élément de la liste si la liste contient 10 éléments?
Et si l'on ne sait pas combien d'éléments elle contient?

Trouver le plus petit élément d'une liste

Pour un humain, trouver le plus petit élément d'une liste consisterait à parcourir cette liste des yeux et il verrait immédiatement le plus petit nombre. Mais si la liste contient des milliers d'éléments? Il faudra adopter une stratégie un peu plus fine. De même, l'ordinateur étant dépourvu de vue et du sens immédiat de "plus petit", "plus grand", il faudra développer une stratégie qui tienne compte de ses capacités (limitées).

Une méthode pourrait être celle-ci

  • considérer le premier élément de la liste et décider que, temporairement, il sera "candidat" à être le plus petit élément
  • parcourir ensuite le reste de la liste, élément par élément
  • si l'on trouve un élément plus petit que notre "candidat", on détrône le candidat et le nouvel élément devient candidat
  • quand on a parcouru toute la liste, on a le plus petit élément

À l'issue de la recherche du plus petit élément de la liste, on peut indiquer son indice (son numéro d'ordre) ou sa valeur, comme on veut.

Ci-dessous, le code python d'une procédure qui permet de trouver le plus petit élément d'une liste.

def minimum (uneListe, debut):
...candidat = uneListe[debut]
...posMinVal = debut
...for i in range (debut+1, len(uneListe)):
......if uneListe[i] < candidat:
.........candidat = uneListe[i]
.........posMinVal = i
...return posMinVal

Quelle est l'instruction qui permet de connaître l'indice du plus petit élément de notre liste?

Cette procédure fournit-elle le plus petit élémnet de la liste ou la position du plus petit élément?

Comment faut-il modifier cette procédure pour qu'elle nous indique le plus grand élément de la liste?

Dites, c'est curieux cet argument "début" pour votre procédure. Il sert vraiment à quelque chose?

Effectivement, j'ai pris un peu d'avance sur la suite. Vous allez voir.

Le tri d'une liste peut donc se faire simplement, maintenant:

  • Passer en revue chacun des éléments de la liste et vérifier s'il est à sa place
  • Rechercher l'élément le plus petit dans la suite de la liste
  • Si ce plus petit est inférieur, permuter les deux éléments
  • Recommencer avec l'élément suivant et le reste de la liste

print(liste) for i in range(0, len(liste)): ...iMin = minimum(liste, i); ...if (liste[iMin] < liste[i]): ......permuter(liste, i, iMin) print(liste)

Dans le code ci-dessus, on a utilisé les procédures "permuter" et "minimum" définies plus haut dans cette page.

  • Que représente la variable iMin dans ce fragment de code?
  • Pourquoi y a-t-il deux fois l'instruction "print(liste)"?
  • À quoi sert le paramètre "i" dans "minimum(liste, i)"?

La vidéo suivante illustre ce tri

Le programme complet (et un peu amélioré) pour ce tri pourrait être

import time
liste = [19,72,43,17,45,42,14,2,27,56]

def permuter (liste, i, j):
...intermediaire = liste[i]
...liste[i] = liste[j]
...liste[j] = intermediaire

def minimum (liste, debut):
...candidat = liste[debut]
...posMinVal = debut
...for i in range (debut+1, len(liste)):
......if liste[i] < candidat:
.........candidat = liste[i]
.........posMinVal = i
...return posMinVal

print(liste)

for i in range(0, len(liste)-1):
...print('Je cherche le minimum de la liste', liste[i:])
...iMin = minimum(liste, i);
...print("J'ai trouvé ",liste[iMin])
...time.sleep(5)
...if (liste[iMin] < liste[i]):
......print('Je permute les nombres ',liste[i],'et',liste[iMin])
......permuter(liste, i, iMin)
......print('Nouvelle liste: ')
...print(liste)

print(liste)

La bibliothèque "time" contient l'instruction "sleep" qui permet de... ralentir l'ordinateur en arrêtant le programme pendant x secondes

La notation liste[2:7] indique la tranche entre l'élément indice 2 et l'élément d'indice 7 d'une liste. La notation liste(i:i+3) indique la tranche entre l'élément d'indice "i" et l'élément d'indice "i+3". La notation liste(i:) désigne la tranche qui commence à l'indice "i" et qui va jusqu'au bout de la liste

En utilisant les informations présentées sur cette page, rédige un programme qui utilise le tri par sélection pour réaliser le tri décroissant des éléments d'une liste.

Quand tu tu as soumis ton travail au professeur, passe à la page suivante. Vers la page suivante Page suivante


Dernière modification 17/10/2018 Test dans /info ...