Cours 6 - Les tris lents

name: inverse
layout: true
class: center, middle, inverse

---
# Inès de Courchelle
## Les tris lents

![image](../img/CY-tech.png)

---
layout: false

# Rappel - Complexité 1/2

.otro-blockquote[Deux algorithmes qui pour les mêmes données d’entrée donnent le même résultat, ne sont pas forcément équivalents.]

---
# Rappel - Complexité 2/2
- Pour un algorithme, on calcule la complexité pour :
  - le meilleur cas
  - le pire cas
  - le cas moyen (on se base sur les probas)
- La complexité est exprimée via \\[Ο\\]
- En algorithme la complexité nous permet de calculer un ordre de grandeur de temps de calculs et de stockages.

#### Par exemple :
\\[ 2N^2 + 3N + 5 \\]

<center>
.underV[La complexité est  Ο(N²);]
</center>

---
# Les tris lents
## Objectifs
- Comprendre les principes et la logique des tris lents
- Calculer la complexité d'un tri lent
- Étudier les problèmatiques liées aux tris

---
# Qu'est ce que le tri ?
## Définition
.otro-blockquote[Algorithme permettant de trier une collection sur un même type dans un ordre précis]

- une collection peut être un tableau 1D, 2D, des couples d'éléments, un annuaire etc ...
- Un ordre de tris peut être décroissant, croissant, ordre alphabétique ...

*Afin d'illustrer les différents algorithme nous utiliserons un tableaux d'entiers à trier par ordre croissant*

---
# Problème du tri
## La complexité

Les paramètres du temps d'exécution d'algorithmes de tris
- La taille du tableau
- L'algorithme utilisé
- La machine exécutant l'algo

**C'est pourquoi l'étude des algorithmes de tri permet d'analyser des problèmes invisibles pendant la phase de codage mais problèmatique durant la mise en service**

---
# Tri par selection
## Définition
- C'est un algorithme de tri par comparaison
- À chaque étape, on met en bonne position l'élément le plus petit

Nous considérons l'exemple suivant :

---
# Tri par sélection
## Step by step
#### Etape 1 : On cherche le plus petit élément
<img src="img/tabselection1.svg"  width=250/>

#### Etape 2 : On met le plus petit élément au bon endroit
<img src="img/tabselection2.svg"  width=250/>

#### Etape 3 : On recommence l'étape 1 et 2 jusqu'au à la fin
<img src="img/tabselection3.svg"  width=500/>

---
# Tri par sélection
## En pseudo code
```c
PROCEDURE triSelection (E/S tab: tableau d'entier,taille : entier)
VARIABLES
    i,j,min : entier
DEBUT
    POUR i de O à taille - 1 FAIRE
        min <- i
        POUR j de i+1 à taille FAIRE
            SI tab[j] < tab[min] ALORS
                min <- j
            FIN SI
        FIN POUR
        echanger(tab,i,min)
    FIN POUR
FIN
```

---
# Procédure echanger
## algo
```c
PROCEDURE echanger (E/S tab : tableau d'entier, i,min : entier)
VARIABLE
    temp : entier
DEBUT
    t <- tab[i]
    tab[i] <- tab[min]
    tab[min] <- t
FIN

```
---
# Procédure echanger
## Illustration
<img src="img/procEchanger1.png" width=750>

---
# Procédure echanger
## Illustration
<img src="img/procEchange2.png" width=750>

---
# Procédure echanger
## Illustration
<img src="img/procEchange3.png" width=750>

---
# Procédure echanger
## Illustration
<img src="img/procEchanger4.png" width=750>

---
# Tri par sélection
## Pendant la phase de codage

- .underR[Fonction ou Procédure ?] .underV[Procédure] avec un pointeur de tableau
- Création d'une procédure d'échange qui prend le tableau, les deux indices à inverser
- Réalisation des commentaires !

## Quelle est la complexité ?
- le meilleur cas
- le pire cas
- le cas moyen

---
# Tri par sélection
## Le pire cas
Le tableau est trié dans le sens inverse

- On considère la taille du tableau par la variable n
<br>
- nombre de comparaisons :

\\[(n-1)+(n-2) ... = {{n(n-1)}\over{2}} \\]

- nombre d'échanges : n/2 si paire et (n-1)/2 si impair

<center> .underV[ Ο(N²)] </center>

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas1.png" width=400>

- nombre de comparaisons : 0
- nombre d'échanges : 0

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas2.png" width=400>

- nombre de comparaisons : 0
- nombre d'échanges : 0

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas3.png" width=400>

- nombre de comparaisons : 1
- nombre d'échanges : 0

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas4.png" width=400>

- nombre de comparaisons : 2
- nombre d'échanges : 0

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas5.png" width=400>

- nombre de comparaisons : 3
- nombre d'échanges : 0

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas6.png" width=400>

- nombre de comparaisons : 4
- nombre d'échanges : 0
---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas7.png" width=400>

- nombre de comparaisons : 5
- nombre d'échanges : 0

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas8.png" width=400>

- nombre de comparaisons : 5
- nombre d'échanges : 1
---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas9.png" width=400>

- nombre de comparaisons : 5
- nombre d'échanges : 1

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas10.png" width=400>

On se positionne sur le 4 et on va le comparer aux autres valeurs du tableau
- nombre de comparaisons : 5
- nombre d'échanges : 1
---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas11.png" width=400>

- nombre de comparaisons : 6
- nombre d'échanges : 1
---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas12.png" width=400>

- nombre de comparaisons : 7
- nombre d'échanges : 1

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas13.png" width=400>

- nombre de comparaisons : 8
- nombre d'échanges : 1

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas14.png" width=400>

- nombre de comparaisons : 9
- nombre d'échanges : 1

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas15.png" width=400>

- nombre de comparaisons : 9
- nombre d'échanges : 2

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas16.png" width=400>

- nombre de comparaisons : 9
- nombre d'échanges : 2

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas17.png" width=400>

On se positionne sur le 3 et on va le comparer aux autres valeurs du tableau

- nombre de comparaisons : 9
- nombre d'échanges : 2

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas18.png" width=400>

- nombre de comparaisons : 10
- nombre d'échanges : 2

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas19.png" width=400>

- nombre de comparaisons : 11
- nombre d'échanges : 2

---
# Tri par sélection
## Le pire cas - illustration

- nombre de comparaisons : 12
- nombre d'échanges : 2

---
# Tri par sélection
## Le pire cas - illustration

- nombre de comparaisons : 12
- nombre d'échanges : 3

---
# Tri par sélection
## Le pire cas - illustration

- nombre de comparaisons : 12
- nombre d'échanges : 3

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas23.png" width=400>

On se positionne sur le 3 et on va le comparer aux autres valeurs du tableau
- nombre de comparaisons : 13
- nombre d'échanges : 3

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas24.png" width=400>

- nombre de comparaisons : 13
- nombre d'échanges : 3

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas25.png" width=400>

- nombre de comparaisons : 14
- nombre d'échanges : 3

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas26.png" width=400>

On se positionne sur le 3 et on va le comparer aux autres valeurs du tableau
- nombre de comparaisons : 14
- nombre d'échanges : 3

---
# Tri par sélection
## Le pire cas - illustration
<img src="img/selectionPireCas27.png" width=400>

- nombre de comparaisons : 15
- nombre d'échanges : 3

#### En général :

- nombre de comparaisons :

\\[(n-1)+(n-2) ... = {{n(n-1)}\over{2}} \\]

- nombre d'échanges : n/2 si paire et (n-1)/2 si impair

---
# Tri par sélection
## Le meilleur cas
Le tableau est déjà trié

- On considère la taille du tableau par la variable n
- nombre de comparaisons :

\\[ (n-1)+(n-2) ... = {{n(n-1)}\over{2}} \\]

- nombre d'échange : 0

<center> .underV[ Ο(N²)] </center>

---
# Tri par sélection
## Le meilleur cas - illustration
On reproduit les mêmes étapes que dans le pire cas sauf que l'on fait JAMAIS d'échange

- nombre de comparaisons : 15
- nombre d'échanges : 0

---
# Tri par sélection
## Le moyen cas
On considère que tous les éléments de la série à trier sont distincts et que toutes leurs permutations sont équiprobables

\\[\sum_{\displaystyle{i=0}}^{\displaystyle{n-1}} i= \frac{n(n-1)}{2}=\frac{n^2}{2}-\frac{n}{2}=O(n^2)
\\]

---
# Tri par sélection
## Autres exemples
<center>
<iframe width="560" height="315" src="https://www.youtube.com/embed/92BfuxHn2XE" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</center>

---
# Tri par sélection
## Autres exemples
<center>
<iframe width="560" height="315" src="https://www.youtube.com/embed/xWBP4lzkoyM" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</center>

---
# Do you wanna dance ?
<center>
<iframe src="https://giphy.com/embed/l4pT3KGvUCxLkfsyI" width="480" height="270" frameBorder="0" class="giphy-embed" allowFullScreen></iframe><p><a href="https://giphy.com/gifs/colbertlateshow-stephen-colbert-jack-black-l4pT3KGvUCxLkfsyI"></a></p>
</center>

---
# Do you wanna dance ?
<center>
<iframe width="560" height="315" src="https://www.youtube.com/embed/Ns4TPTC8whw" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</center>

---
# Tri à Bulles
## Définition

- C'est un algorithme de tri par comparaison
- Tout élément doit être plus petit que celui qui suit

On reprend l'exemple d'avant :

---
# Tri à Bulles
.under[Etape 1 : on parcours le tableau]
- si l'élément courant "a" est plus grand que l'élément suivant "b",
- Alors on les inverse

.under[Etape 2 : on compte]
- Si un élément est changé de place,
- Alors on comptabilise le changement

---
# Tri à Bulles
.under[Etape 3 : Est ce que mon tableau est trié ?]

.underR[Non !] (Le seul élément trié est le 90 !) .underV[Alors, je recommence !]
<center>
    <img src="img/tabbulle3.png"  width=670/>
</center>

---
# Tri à Bulles
.under[Etape 4 : Il faut que je m'arrête !!]
<center>
    <img src="https://media.giphy.com/media/TabwFck9vEt44/giphy.gif"  width=500/>
</center>

.underV[Mais Comment ?]

---
# Tri à Bulles
.under[Etape 5 : Dès que le tableau est trié !]
<center>
    <img src="https://media.giphy.com/media/l3HBbltOYjoNq/giphy.gif"  width=300/>
</center>

.underV[Mais Encore ?]

---
# Tri à Bulles
.under[Etape 5 : Dès qu'aucun échange n'aura été réalisé !]
<center>
    <img src="img/tabbulle4.png"  width=670/>
</center>

---
# Tri à Bulles
## En pseudo code
```c
PROCEDURE triBulle(tab : pointeur de tableau d entier, taille : entier)
VARIABLES
    j : entier
    enDesordre : booleen
DEBUT
    enDesordre <- vrai
    TANT QUE (enDesordre) FAIRE
        enDesordre <- faux
        POUR j de 0 à taille -1 FAIRE
            SI tab[j] > tab[j+1]
                echanger(tab,j,j+1)
                enDesordre <- vrai
            FIN SI
        FIN POUR
    FIN TANT QUE
FIN
```

---
# Tri à Bulles
## Illustration

<img src="img/triABulle1.png"  width=670/>
---