## les tris
---


## Prérequis

Les élèves doivent être à l'aise avec : 
- Notions transversales de programmation
- les listes
- les boucles
- les structures conditionnelles
- opérateurs booléens


### Eléments de programme abordés

- indexation des tables (importer une table depuis un fichier CSV)
- recherche dans une table
- tris par insertion et sélection
- fusion de tables


## Activité découverte

[Activité découverte prof](activiteDecouverte\Activitédedécouverteprofs.pdf)

[Vidéo](activiteDecouverte\Vidéos\Algorithme1.mp4)


## COURS
---
1er algorithme


### Que fait ce code ?

```python
    for k in range(i+1, n):
        if T[k] < T[pMin]:
            pMin = k
```


### Réponse

Ces lignes de code parcourent le reste du tableau à partir d'un indice de début (i+1) et recherchent le dernier élément le plus petit.  L'indice est mémorisé dans pMin. Il s'agit de la boucle intérieure.

![Autodesk](images/tri1.png)![Autodesk](images/tri2.png)


### Que fait ce code ?

```python

    tmp = T[i]      
    T[i] = T[pMin]  
    T[pMin] = tmp   

```


### Réponse

Le code permute 2 valeurs du tableau. 'tmp' est le nom de la variable temporaire permettant de mémoriser la valeur qui sera permutée.

![Autodesk](images/tri2.png)![Autodesk](images/tri3.png)


### Réponse (suite)

![Autodesk](images/tri4b.png)


### Synthèse

En associant les lignes de code précédentes :

```python

    for k in range(i+1, n):
        if T[k] < T[pMin]:
            pMin = k
    tmp = T[i]      
    T[i] = T[pMin]  
    T[pMin] = tmp   
```
Elles permettent donc de comparer (pour l'instant) un élément du tableau avec l'ensemble des éléments restant afin d'y trouver un élément qui pourrait lui être inférieur. Dans ce cas la permutation est effectuée.


## Généralisation

Le code doit être généralisé pour l'ensemble du tableau. On y intègre  une boucle plus globale, appelée boucle extérieure, qui parcourt l'ensemble des valeurs du tableau.


## Tri par sélection

L'algorithme présenté est un algorithme de tri nommé 'tri par sélection' dont le principe est d'aller chercher le plus petit élément du tableau pour le mettre en premier, puis de repartir de l'élément suivant et de recommencer.

```python
def triSelection(T):
    n = len(T)
    for i in range(0, n-1):
        pMin = i
        for k in range(i+1, n):
            if T[k] < T[pMin]:
                pMin = k
        tmp = T[i]      
        T[i] = T[pMin]  
        T[pMin] = tmp   
    return c

```


## Pratique

A l'aide du programme de tri par sélection et de la liste fournie, exécuter le code et afficher la liste triée pour constaster son bon fonctionnement.
```python
tableau = [20,19,18,17,16,15,14,13,12,11,10,9, 8, 7, 6, 5, 4, 3, 2, 1]
```


## 2e algorithme


## Code

Que fait ce code ?

```python
def tri_insertion(tableau):
    for i in range(1,len(tableau)):
        en_cours = tableau[i]
        j = i
        #.....
        while j>0 and tableau[j-1]>en_cours:
            tableau[j]=tableau[j-1]
            j = j-1
        #.....
        tableau[j]=en_cours
```


## Tri par insertion
(éléments de correction)
- Pour i de 1 à la longueur du tableau
- La variable en_cours prends la valeur dans la case i
- La variable j prend la valeur de i
- Tant que j et supérieur à 0 et que la valeur dans la case j-1 et supérieur à en_cours
- Mettre la valeur situé dans la case j-1 dans la case j
- La case j prend la valeur de la -variable en_cours


## Pratique

A l'aide du programme de tri par insertion et de la liste fournie, exécuter le code et afficher la liste triée pour constaster son bon fonctionnement.
```python
tableau = [20,19,18,17,16,15,14,13,12,11,10,9, 8, 7, 6, 5, 4, 3, 2, 1]
```


## Question 

Est il possible de trier un fichier volumineux ?

A l'aide du fichier HADOPI.csv fourni, classer par ordre croissant l'âge des personnes ayant reçu un mail d'avertissement de la part d'HADOPI.

Suivre les consignes qui suivent.


## Lire un fichier CSV

installer la bibliothèque PANDAS et ajouter : 

```python
import pandas as pd
```

Lire le fichier et importer la colonne dans un tableau
```python
fichier=pd.read_csv('HADOPI_-_2018.csv',";")
tableau=fichier['nomDeLaColonne']
```


Exécuter les 2 algorithmes de tri

 Que remarquez-vous ?


## une autre méthode de tri

Transformer le tableau importé en liste  afin d'utiliser la méthode de tri de python.

```python
listeDonnees = list(tableau)
listeDonnees.sort()
```


Que remarquez-vous ?


## Bonus

[Quel est l'algorithme de tri présenté dans cette vidéo ?](activiteDecouverte\Vidéos\Algorithme2.mp4)


## Exercices

[ici](exercices\Exercice_prof.pdf)


## Ressources

[http://lwh.free.fr/pages/algo/algorithmes.html]