tris quadratiques et tri à partir d'une cle

Utiliser Pyzo, ou IDLE ou autre IDE Python pour ce TP. Les 3 parties sont indépendantes, et peuvent être placées dans 3 fichiers python différents.

Partie 1: découvrir le tri par insertion et par séléction

Tri par insertion

Ecrire en utilisant uniquement des lignes de code choisies parmi les lignes suivantes, une fonction de tri par insertion qui retourne la liste placée en argument avec ses éléments classés par ordre croissant. Les lignes ne sont pas toutes à utiliser et l’indentation est à adapter.

def tri_insertion(liste):
for i in range(1, len(liste)):
for i in range(len(liste)-1):
valeur = liste[i]
valeur = liste[0]
j = i
j = i - 1
while j >= 0 and liste[j] > valeur:
while j > 0 and liste[j] >= valeur:
liste[j] = liste[j-1]
liste[j + 1] = liste[j]
j -= 1
j += 1
liste[j + 1] = valeur
liste[j] = valeur
return liste
return liste.copy()

Utiliser cette fonction pour trier chacune des listes suivantes:

L1 = [19, 8, 10, 1, 2, 50, 3, 5]
L2 = ['z', 'y', 'x', 'w', 'v', 'u']

Ajouter une instruction dans la fonction tri_insertion pour suivre l’évolution du tri à chaque tour de la boucle externe.

Recopier et completer le tableau de suivi (cahier):

tour	`i`	`L1`
debut du tour 1	1	`[19, 8, 10, 1, 2, 50, 3, 5]`
fin du tour 1	1
fin du tour 2	2
fin du tour 3	3
fin du tour 4	4
fin du tour 5	5
fin du tour 6	6
fin du tour 7	7

Ecrire une fonction est_triee pour vérifier si les éléments d’une liste sont placés dans l’ordre croissant.

Utiliser la base suivante pour la fonction: (et compléter):

def est_triee(L):
    for i in range(1,len(L)):
        if ...:
            return False
    return ...

Ajouter un test d’assertion pour chacune de ces listes pour vérifier que la fonction a bien effectué le tri sur ces listes.

Tri par séléction

Ecrire la fonction tri_selection à partir des lignes suivantes (idem question 1 plus haut)

def tri_selection(liste):
for i in range(len(liste)):
for i in range(len(liste)-1):
indice_min = 0
indice_min = i
for j in range(i, len(liste)-1):
for j in range(i + 1, len(liste)):
if liste[j] < liste[indice_min]:
if liste[j] > liste[indice_min]:
indice_min = j
j = indice_min
liste[i], liste[indice_min] = liste[indice_min], liste[i]
liste[indice_min] = liste[i]
liste[i] = liste[indice_min]
return liste
return liste.copy()

Utiliser cette fonction pour trier chacune des listes suivantes:

L1 = [19, 8, 10, 1, 2, 50, 3, 5]
L2 = ['z', 'y', 'x', 'w', 'v', 'u']

Ajouter une instruction dans la fonction tri_insertion pour suivre l’évolution du tri à chaque tour de la boucle externe.

Recopier et completer le tableau de suivi:

tour	`i`	`L1`
debut du tour 1	0	`[19, 8, 10, 1, 2, 50, 3, 5]`
fin du tour 1	0
fin du tour 2	1
fin du tour 3	2
fin du tour 4	3
fin du tour 5	4
fin du tour 6	5

Question 1: le tableau est-il différent de celui obtenu pour le tri par insertion? Quelles sont ces différences?

Ajouter les tests d’assertion pour vérifier que la fonction a bien effectué le tri sur ces listes.

Partie 2: Appliquer un algorithme de tri

Nous allons appliquer les 2 algorithmes de tri (insertion et selection) sur des listes non ordonnées.

Mélanger un liste de mots

(1) Télécharger et placer le fichier index de mots français pli07.zip. Dézipper ce fichier dans un dossier que vous appelerez recherche_et_tri.
(2) Ouvrir un nouveau fichier python dans le même dossier. Placer l’import des librairies random et time à l’ouverture de ce fichier (premières lignes):

import random,time

(3) Ajouter au script python les fonctions de tri vues dans le cours: Lien vers le cours
(4) importer une liste de mots d’un dictionnaire non accentué. Appeler cette liste mots.

with open('pli07.txt', encoding='utf-8') as f:
    for mot in f.read().splitlines():
        mots.append(mot)

(5) mélanger la liste de mots avec la fonction random.shuffle (voir exemple plus bas)
(6) réduire cette liste à seulement 10000 mots: mots = mots[:10000]
(7) copier cette liste de mots (faire une copie par valeur): mots_melanges = mots.copy()

Aide:

La fonction shuffle du module random permet de mélanger en place les éléments d’une liste. Exemple:

> import random
> L = [3, 4, 6, 8, 10, 20]
> random.shuffle(L)
> L
# exemple d'affichage
[6, 3, 20, 10, 8, 4]

(8) Programmer une fonction est_triee qui vérifie si la liste est bien triée. Cette fonction sera utile pour contrôler que la fonction de tri effectue bien le tri demandé. (voir partie 1)
(9) Utiliser cette fonction pour vérifier que la liste mots est mélangée:

> est_triee(mots)
False

Trier le dictionnaire de mots

Votre script devrait avoir l’allure suivante: (Voir l’aide)

Aide

import random
import time

def est_triee(L):
    pass

def tri_insertion(L):
    pass

def tri selection(L):
    pass

mots = []
# Lecture du fichier txt et remplissage de la liste
with open(...) as f:
    for mot in f.read().splitlines():
        mots.append(mot)

mots = mots[:10000]
random.shuffle(...)
mots_melanges = ... .copy()

Vous allez tester maintenant vos fonctions de tri sur la liste de mots, une fois celle-ci mélangée et placée dans une copie.

Question 2: Mesurer le temps mis pour trier la liste de mots à l’aide du tri par insertion. (faire plusieurs essais).

Remarque: Si vous voulez comparer 2 algorithmes de tri en place, sur la même liste, il faudra utiliser une copie par valeur de la liste mélangée. Le tri par insertion puis par selection doit être realisé sur la MEME liste si vous voulez comparer les durées de traitement.

On rappelle que la mesure du temps peut être réalisée de la manière suivante:

Pour le tri par insertion:

start_time = time.time()
tri_insertion(mots)
stop_time = time.time()
interval1 = stop_time - start_time

Question 3: Mesurer le temps mis pour trier la liste de mots à l’aide du tri par selection. (faire plusieurs essais). Comparer le temps mis par les 2 algorithmes de tri. Conclure.
Question 4: Evaluer la complexité algorithmique pour chacun de ces algorithmes. Les résultats mesurés sont ils conformes à ce qui est attendu?

Partie 3: TP tri à partir d’une clé

On peut réaliser un tri à l’aide d’une clé. Les objets (les lignes d’un fichier csv) contiennent ainsi des valeurs sur plusieurs colonnes. On peut choisir l’une de ces colonnes pour réaliser le tri.

On prendra pour exemple le fichier du classement UEFA des équipes feminines sur plusieurs années. Le tableau est consultable à la page de l’UEFA.com

import du fichier csv

-> fichier csv classement_uefa.csv à telecharger

Ci-dessous, le programme minimal pour lire le fichier csv. Testez le à l’aide d’un IDE (Pyzo ou autre). Adaptez si necessaire le chemin vers le fichier:

import csv
with open('classement_uefa.csv', newline='') as csvfile:
    spamreader = csv.reader(csvfile, delimiter = ";")
    teams = []
    for row in spamreader:
        teams.append(row)
print(teams[0])
# affiche
['\ufeffClub', 'Pays', '16/17', '17/18', '18/19', '19/20', '20/21', '\xa0pts\xa0', '\xa0Ass\xa0']

La premiere ligne contient l’en-tête du tableau. Il faudra supprimer cette premiere ligne:

del(teams[0])
print(teams[0])
# affiche
['AC Sparta Praha', 'CZE', '3', '9', '3', '3', '8', '26', '11,715']

Nettoyer les données

La valeur de la colonne d’indice 8 contient la chaine de caractères (str) '11,715'. Il faudra transformer cette valeur en (float) 11.75

Même traitement avec la colonne 7.

On peut utiliser la méthode de chaine replace:

team = teams[0]
team[7] = team[7].replace(',','.')
team[8] = team[8].replace(',','.')
print(team)

Importer à nouveau le tableau source, puis faire ce traitement sur les 114 équipes du tableau teams. (Utiliser une boucle for)

Classement par indice UEFA: colonne 7

Au depart les équipes sont classées par ordre alphabetique:

['AC Sparta Praha', 'CZE', '3', '9', '3', '3', '8', '26', '11.715']
['AFC Ajax', 'NED', '-', '5', '8', '-', '3', '16', '9.9']
['Akadimia Elpides Karditsas', 'GRE', '-', '-', '2', '-', '-', '2', '2.145']
['ALG Spor Kulübü Derneği', 'TUR', '-', '-', '-', '-', '0', '0', '2.145']
['Apollon Ladies FC', 'CYP', '4', '3', '-', '2', '0', '9', '4.62']
...

On veut adapter l’agorithme de tri par selection pour classer les equipes selon une clé, qui sera l’indice de la colonne contenant les points UEFA de l’équipe.

A vous de jouer: adapter le script des algorithmes de tri:

Ajouter un nouveau paramètre cle aux fonctions tri_insertion et tri_selection.

Adapter les programmes des 2 fonctions pour trier par rapport à une clé. Modifier par exemple la condition dans la boucle for de la fonction de recherche du minimum (ttri par selection) avec if T[k][cle]<T[indiceDuMin][cle] :

Trier maintenant la liste teams selon la colonne de rang 7.

Si vous affichez cette liste, elle presente 2 inconvenients:

elle est triée telle que l’equipe la plus faible est au debut du tableau et la meilleure à la fin.
l’affichage ne facilite pas la lecture

Modifier la fonction de tri pour réaliser un tri par l’élément le plus grand d’abord.

Question 5: Quel est le classement UEFA des équipes entre la $1^{ere}$ et la $5^e$ equipe?

Classement par coefficient des associations: colonne 8

Le classement par coefficient des associations ou des pays prend en compte les résultats de tous les clubs d’une association. Il est utilisé pour déterminer le nombre de clubs que pourra engager une association dans les compétitions de l’UEFA les saisons suivantes. C’est la valeur de la colonne 8.

Classer les équipes par coefficient des associations.

Question 6: Quel est le nouveau classement des équipes entre la $1^{ere}$ et la $5^e$ equipe?

Nettoyer les résultats

On souhaite obtenir l’affichage suivant, avec seulement les colonnes equipe, pays, indice uefa:

0 ('Olympique Lyonnais', 'FRA', '99')
1 ('FC Barcelona', 'ESP', '78')
2 ('VfL Wolfsburg', 'GER', '77')
3 ('Paris Saint-Germain', 'FRA', '60')
4 ('Manchester City WFC', 'ENG', '59')
5 ('FC Bayern München', 'GER', '57')
6 ('Chelsea FC Women', 'ENG', '45')
...

Ajouter les instructions suivantes qui permettront d’afficher les equipes :

Créer un tableau vide T.
faire une boucle bornée for sur la liste teams : for t in range(...)
Dans la boucle for, à chaque itération, ajouter dans T un tuple constitué des colonnes 0, 1 et 7 pour chacune des équipes.
afficher classement et equipe avec : print(t,T[t])

Liens

Cours/TD de mcoillac sur le tri par insertion et le tri par selection