Cours 7 - Les tris rapides

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

---
# Inès de Courchelle
## Les tris rapides
## 2023-2024

---
layout: false

# Rappel -Tris Lents 1/4
## Tri selection
```c
PROCEDURE triSelection (E/S tab: tableau d'entiers,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]
                min <- j
            FIN SI
        FIN POUR
        echanger(tab,i,min)
    FIN POUR
FIN
```
---
# Rappel - Tris Lents 2/4
## Tri à bulle
```c
PROCEDURE triBulle(E/S tab: tableau d'entiers, taille : entier)
VARIABLES
    j,enDesordre : entier
DEBUT
    enDesordre <- 1
    TANT QUE (enDesordre)
        enDesordre <- 0
        POUR j de 0 à taille -1 FAIRE
            SI tab[j] > tab[j+1]
                echanger(tab,j,j+1)
                enDesordre <- 1
            FIN SI
        FIN POUR
    FIN TANT QUE
FIN
```

---
# Rappel - Tris Lents 3/4
## Tri par Insertion
```c
PROCEDURE triInsertion(E/S tab: tableau d entier, taille : entier)
VARIABLES
    i,j, eltEnCours : entier
DEBUT
    POUR i de 1 à taille FAIRE
        eltEnCours <- tab[i]
        POUR j de i à 0 ET tab[j-1] > eltEnCours FAIRE
            tab[j] <- tab[j-1]
        FIN POUR
        tab[j] = eltEnCours
    FIN POUR
FIN
```
---
# Rappel - Tris Lents 4/4
## La complexité

| algo      | pire          | meilleur      | moyen         |
| --        | --            | --            | --            |
| Sélection | Ο(N²) | Ο(N²) | Ο(N²) |
| Bulles    | Ο(N²) | Ο(N)  | Ο(N²) |
| Insertion | Ο(N²) | Ο(N)  | Ο(N²) |

---
# La rapidité
## Objectifs

- Comprendre les principes et la logique des tris rapides
- Calculer la complexité d'un tri rapide
- Analyser le tri rapide, et le tri fusion
- Comparer les tris lents avec les tris rapides

---
# Tri rapide
## Principes

- Il s'appel pareil !
- Diviser pour mieux régner
- Utiliser une valeur de référence
- L’algorithme de tri est récursif sur les tableaux ségmentés

## Les étapes
- Sélectionner une valeur pivot dans le tableau
- Déplacer avant elle toutes les valeurs inférieures au pivot
- Ré-itérer le procédé sur la tranche de tableau inférieur et supérieur au pivot
<img src="https://media.giphy.com/media/u5bbqJE63sBGM/giphy.gif"  width=400/>

---
# Tri rapide
## Illustration
Nous considérons le tableau suivant :
<img src="img/C-tri-rapide.svg"  width=400/>

#### Etape 1 : Le pivot

On choisit souvent le premier élément du tableau !

---
# Tri rapide
## Illustration
#### Etape 2 : On décale les élèments plus petit que le pivot à gauche !
<img src="img/tri-rapide2.svg"  width=500/>

.underV[On obtient :]

---
# Tri rapide
## Illustration
#### Etape 3 : On sélectionne un pivot dans le tableau à Gauche et dans le tableau à Droite

.underV[Comme si on avait 2 sous-tableaux :]
<img src="img/tri-rapide3bis.svg"  width=500/>

---
# Tri rapide
## Illustration
#### Etape 4 : On décale les élèments plus petit que le pivot à gauche !
<img src="img/tri-rapide4.svg"  width=500/>

.underV[On obtient :]
.pull-left[

]
.pull-right[

]

<br>
.underV[Soit :]

---
# Tri rapide
## Illustration
#### Etape 5 : Dans les nouveaux sous-tableaux on choisit un pivot !

.pull-left[

]
.pull-right[

]

---
# Tri rapide
## Illustration
#### Etape 6 : On décale les élèments plus petit que le pivot à gauche !

.underV[On a donc :]

---
# Tri rapide
## Illustration
#### Etape 7 : Dans les nouveaux sous-tableaux on choisit un pivot !
.pull-left[

]
.pull-right[

]

.underV[On a donc :]

---
# Tri rapide
## Pseudo code
```c
PROCEDURE triRapide (E/S tab: tableau d'entiers, p,r: entier)
VARIABLE :
    q : entier
DEBUT
    SI p < r FAIRE
        q <- partitionner(tab,p,r)
        triRapide(tab,p,q)
        triRapide(tab,q+1,r)
    FIN SI
FIN
```
---
# Tri rapide
## Pseudo code
```c
FONCTION partitionner (E/S tab: tableau d'entiers, p,r : entier) : entier
VARIABLES :
    pivot, i,j : entier
DEBUT
    pivot<-tab[p]
    i<- p-1
    j<- r+1
    TANT QUE (i<j) FAIRE
        FAIRE
           j <- j-1
        TANT QUE (tab[j] > pivot)
        FAIRE
           i <- i+1
        TANT QUE (tab[i] < pivot)
        SI (i<j) ALORS
           echanger(tab,i,j)
        FIN SI
    FIN TANT QUE
    retourner (j)
FIN
```

---
# Tri rapide
## Les appels récursifs
#### Appel initial
.pull-left[
```c
triRapide([5, 8, 3, 2, 1], 0, 4)
```
]
.pull-right[
```c
PROCEDURE triRapide (E/S tab: tableau d'entiers, p,r: entier)
VARIABLE :
    q : entier
DEBUT
    SI p < r FAIRE
        q <- partitionner(tab,p,r)
        triRapide(tab,p,q)
        triRapide(tab,q+1,r)
    FIN SI
FIN
```
]
---
# Tri rapide
## Les appels récursifs
.pull-left[
```c
triRapide([5, 8, 3, 2, 1], 0, 4)
```
.under[est ce que p<r ?]

.underV[YES]

0 < 4
```c
q <- partitionner(tab,p,r)
```
tab .arrow[] [5, 8, 3, 2, 1]

p .arrow[] 0

r .arrow[] 4
]
.pull-right[
```c
PROCEDURE triRapide (E/S tab: tableau d'entiers, p,r: entier)
VARIABLE :
    q : entier
DEBUT
    SI p < r FAIRE
        q <- partitionner(tab,p,r)
        triRapide(tab,p,q)
        triRapide(tab,q+1,r)
    FIN SI
FIN
```
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
q <- partitionner(tab,p,r)

tab .arrow[] [5, 8, 3, 2, 1]

p .arrow[] 0

r .arrow[] 4

pivot .arrow[] 5

i .arrow[] -1

j .arrow[] 5

]
.pull-right[
<img src="img/triRapideExemple1.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

j .arrow[] 5

i .arrow[] -1

Boucle N°0 :
```c
TANT QUE (i < j)
```

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

j .arrow[] 5

pivot .arrow[] 5

Boucle N°1 :
```c
FAIRE
    j <- j-1
TANT QUE (tab[j] > pivot)
```

j .arrow[] 4

.under[1 > 5 ?] .underR[NOPE]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

j .arrow[] 4

pivot .arrow[] 5

Boucle N°1 :
```c
FAIRE
    j <- j-1
TANT QUE (tab[j] > pivot)
```

j .arrow[] 3

.under[2 > 5 ?] .underR[NOPE]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

j .arrow[] 3

pivot .arrow[] 5

Boucle N°1 :
```c
FAIRE
    j <- j-1
TANT QUE (tab[j] > pivot)
```

j .arrow[] 2

.under[3 > 5 ?] .underR[NOPE]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

j .arrow[] 2

pivot .arrow[] 5

Boucle N°1 :
```c
FAIRE
    j <- j-1
TANT QUE (tab[j] > pivot)
```

j .arrow[] 1

.under[8 > 5 ?] .underV[YES]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

i .arrow[] -1

pivot .arrow[] 5

Boucle N°2 :
```c
FAIRE
    i <- i-1
TANT QUE (tab[i] < pivot)
```

i .arrow[] 0

.under[5 > 5 ?] .underR[NOPE]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

i .arrow[] 0

pivot .arrow[] 5

Boucle N°2 :
```c
FAIRE
    i <- i-1
TANT QUE (tab[i] < pivot)
```

i .arrow[] 1

.under[8 > 5 ?] .underR[NOPE]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

i .arrow[] 1

pivot .arrow[] 5

Instruction SI  :
```c
SI (i<j) ALORS
    echanger(tab,i,j)
FIN SI
```

i .arrow[] 1
j .arrow[] 1

.under[1 < 1 ?] .underR[NOPE]

]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels récursifs
.pull-left[
tab .arrow[] [5, 8, 3, 2, 1]

j .arrow[] 1

i .arrow[] 1

Boucle N°0 :
```c
TANT QUE (i < j)
```

.under[1<1] ? .underR[NOPE]

On sort de la boucle

et on retourne J
]
.pull-right[
<img src="img/triRapideExemple2.png" width=400>
]

---
# Tri rapide
## Les appels
.pull-left[
On repart dans la prodédure principale
q .arrow[] 1
p .arrow[] 0
r .arrow[] 4

Et on refait appel :
  - triRapide(tab,p,q) => triRapide(tab,0,1)
  - triRapide(tab,q+1,r) => triRapide(tab,2,4)
]
.pull-right[
```c
PROCEDURE triRapide (E/S tab: tableau d'entiers, p,r: entier)
VARIABLE :
    q : entier
DEBUT
    SI p < r FAIRE
        q <- partitionner(tab,p,r)
        triRapide(tab,p,q)
        triRapide(tab,q+1,r)
    FIN SI
FIN
```
]

---
# Tri rapide
## Le pire cas
- Un des deux tableaux est vide à chaque appel de la fonction tri.
- Cela arrive lorsque le tableau est déjà trié.
- Ici, p est l'appel de la fonction partition.

\\[C(n) =  p(n)+C(0)+C(n-1)  \\]
\\[C(n) =  p(n)+ p(n)+C(n-2)  \\]
\\[C(n) = 2p(n)+p(n)+C(n-3)  \\]
\\[C(n) = 3p (n) +C(n-3)\\]
\\[     ... \\]
\\[ C(n) = n  \times p(n) + C(n-n) \\]
\\[ C(n) = n  \times p(n) + C(0) \\]

---
# Tri rapide
## Le pire cas
\\[ C(n) = n  \times p(n) + C(n-n) \\]
\\[ C(n) = n  \times p (n) + C(0) \\]
- p(n) a une complexité de  Ο(N)
- DONC \\[ n \times p (n) \\]

---
# Tri rapide
## Le pire cas
- .underV[La complexité est  Ο(N²)]

- Les deux tableaux sont de la même taille à chaque appel de la fonction tri.
- Cela arrive lorsque le tableau est déjà trié.

---
# Tri rapide
## Le moyen cas
- Dans le cas le plus équilibré, les tailles des deux tableaux suivent une loi uniforme sur [0,n-1].
- C'est-à-dire, que la probalité de choix d'une case est la même.
\\[ C(n) = p(n) + C(\frac{n}{2}) +  C(\frac{n}{2})  \\]

.pull-left[
.underV[ICI la partie gauche :]
\\[ C(\frac{n}{2}) \\]
.underV[ICI la partie droite :]
\\[ C(\frac{n}{2}) \\]
]

.pull-right[

]

---
# Tri rapide
## Le moyen cas
On obtient :
\\[ C(n) = p(n) + 2C(\frac{n}{2}) \\]
n est un entier, or  :
\\[ \frac{n}{2} \\]
1. .underR[ne donne pas toujours un résultat entier]
2. .under[On ne peut donc pas établir de relation récurente]

.pull-left[
.underV[Solution :] Changement de variable
\\[ n= 2^k \\]
]
.pull-right[
.underV[Justification du choix :] <br>
   on aura toujours un résultat en entier
]

---
# Tri rapide
## Le moyen cas
\\[ C(n) = p(n) + 2C(\frac{n}{2}) \\]
Avec le Changement de variable :
\\[ n= 2^k \\]

\\[ C(2^k)  = 2C(\frac{2^k}{2})+p(2^k) \\]
\\[ C(2^k)= 2C(2^{k-1})+p(2^{k})  \\]
\\[ C(2^k)= 2[2C(2^{k-2})+p(2^{k-1})]+p(2^{k}) \\]

---
# Tri rapide
## Le moyen cas
\\[ C(2^k)= 2^2C(2^{k-2})+p(2^{k})+p(2^{k}) \\]
\\[ C(2^k)= 2^2C(2^{k-2})+2p(2^{k})  \\]
\\[ C(2^k)= 2^2[C(2^{k-3})+p(2^{k-2})]+2(p(2^{k}) \\]
\\[ C(2^k)= 2^3C(2^{k-3})+2p(2^{k})+p(2^k) $ \\]
\\[ C(2^k)= 2^3C(2^{k-3})+3p(2^{k}) $ \\]
\\[ ... \\]
En Fonction de k :
\\[ C(2^k)= 2^kC(2^{k-k}) + kp(2^{k}) \\]
\\[ C(2^k)= 2^kC(1) + kp(2^{k}) \\]

---
# Tri rapide
## Le moyen cas

\\[ C(2^k)= 2^kC(1) + kp(2^{k}) \\]
Changement variable inverse (pour revenir à une notation avec n)
\\[ n=2^k  \\]
Il faut isoler le k
\\[ n=2^k \Leftrightarrow ln(n)=ln(2^k) \\]
\\[ n=2^k \Leftrightarrow ln(n)=k~ln(2) \\]
\\[ n=2^k \Leftrightarrow k= \frac{ln(n)}{ln(2)} \\]
\\[ n=2^k \Leftrightarrow k= n log (n) \\]
\\[ C(n)= n \times C(1)  + n log (n) \times p (n) \\]

.underV[O(n log n)]

---
# Tri rapide
## Le meilleur cas
- Relativement la même !
- L'ensemble doit systématiquement partitionné selon la valeur au milieu.
- Les deux partitions auront toujours plus ou moins la même taille
- La moitié de la taille d'origine.
- La profondeur de récursion atteindrait alors log(n) (on divise par deux à chaque fois !)
- Et comme à chaque niveau on effectue n opérations pour le partitionnement
- On a bien une complexité de .underV[O(n log(n))]

---
# Tri rapide
## Autres exemples

---
# Tri rapide
## Autres exemples

---
# Do you wanna dance ?

---
# Tri fusion
## Principes
- Diviser pour mieux régner à traver deux parties séparées
- Si le tableau est de taille réduite on peut facilement le résoudre.
- Structure récursive : pour résoudre un problème donné, l’algorithme s’appelle lui même
- En anglais, merge sort !

## 3 étapes de niveau de récursivité
- Diviser le tableau en plusieurs sous tableau
- Régner sur les différents tableaux
- Combiner les différents tableaux entres eux

---
# Tri fusion
## Illustration
<img src="img/fusionExemple.svg"  width=500/>

---
## La blagounette
Il faut s'imaginer que tri fusion en anglais ça se dit merge sort (sinon ça marche pas)!

---
# Tri fusion
## Pseudo code
```c
PROCEDURE triFusion (E/S tab : tableau d'entiers,
                        monDebut : entier, maFin : entier)
VARIABLE :
    milieu : entier
DEBUT
    SI monDebut< maFin
        milieu <-(monDebut+maFin)/2;
        triFusion(tab, monDebut, milieu);
        triFusion(tab, milieu+1, maFin);
        fusionner(tab,monDebut,milieu,maFin);
    FIN SI
FIN

```

---
# Tri fusion
## Pseudo code 1/3
```c
PROCEDURE fusionner (E/S tab: tableau d'entiers, monDebut : entier,
                        monMilieu : entier, maFin : entier)

VARIABLES :
    i,max : entier
    gauche,droite : entier
    tabTemp : tableau d'entiers
DEBUT
 i<-0
 max<-maFin-monDebut
 gauche<-monDebut
 droite<- monMilieu+1
```
---
# Tri fusion
## Pseudo code 2/3
```c
 TANT QUE gauche<=monMilieu ET droite <= maFin
    SI tab[gauche]<tab[droite]
        tabTemp[i]<-tab[gauche]
        gauche<-gauche+1
    SINON
        tabTemp[i]<-tab[droite]
        droite<-droite+1
    FIN SI
    i<-i+1
 FIN TANT QUE
```
---
# Tri fusion
## Pseudo code 3/3
```c
 TANT QUE gauche <= monMilieu
    tabTemp[i]=tab[gauche];
    gauche<-gauche+1
    i<-i+1
 FIN TANT QUE

TANT QUE droite <= maFin
    tabTemp[i]<-tab[droite]
    droite<-droite+1
    i<-i+1
 FIN TANT QUE

POUR i allant de 0 à max+1 FAIRE
    tab[i+monDebut]<-tabTemp[i]
 FIN POUR
FIN
```
---
# Tri fusion
## Appel Initial
```c
triFusion(TABLEAU,0,TAILLE-1);
```

---
# Tri fusion
## Mise en garde
- Besoin d'un tableau temporaire !
- Tableau de pointeur DONC il faut un malloc (allouer)
- un malloc = un free
- Il faut donc libérer la mémoire avant la fin de la procédure fusionner !

---
# Tri fusion
## Le moyen cas
- Dans le cas le plus équilibré, les tailles des deux tableaux suivent une loi uniforme sur [0,n-1].
- C'est-à-dire, que le tableau est divisé en deux partie égale à chaque étape
\\[ C(n) = f(n) + C(\frac{n}{2}) +  C(\frac{n}{2})  \\]

.pull-left[
.underV[ICI la partie gauche :]
\\[ C(\frac{n}{2}) \\]
.underV[ICI la partie droite :]
\\[ C(\frac{n}{2}) \\]
]

.pull-right[

]

---
# Tri fusion
## Le moyen cas
On obtient :
\\[ C(n) = f(n) + 2C(\frac{n}{2}) \\]
n est un entier, or  :
\\[ \frac{n}{2} \\]
1. .underR[ne donne pas toujours un résultat entier]
2. .under[On ne peut donc pas établir de relation récurente]

.pull-left[
.underV[Solution :] Changement de variable
\\[ n= 2^k \\]

]
.pull-right[

.underV[Justification du choix :] <br>
   on aura toujours un résultat en entier

]

---
# Tri fusion
## Le moyen cas
\\[ C(n) = f(n) + 2C(\frac{n}{2}) \\]
Avec le Changement de variable :
\\[ n= 2^k \\]

\\[ C(2^k)  = 2C(\frac{2^k}{2})+f(2^k) \\]
\\[ C(2^k)= 2C(2^{k-1})+f(2^{k})  \\]
\\[ C(2^k)= 2[2C(2^{k-2})+f(2^{k-1})]+f(2^{k}) \\]

---
# Tri fusion
## Le moyen cas
\\[ C(2^k)= 2^2C(2^{k-2})+f(2^{k})+f(2^{k}) \\]
\\[ C(2^k)= 2^2C(2^{k-2})+2f(2^{k})  \\]
\\[ C(2^k)= 2^2[C(2^{k-3})+f(2^{k-2})]+2(f(2^{k}) \\]
\\[ C(2^k)= 2^3C(2^{k-3})+2f(2^{k})+f(2^k) $ \\]
\\[ C(2^k)= 2^3C(2^{k-3})+3f(2^{k}) $ \\]
\\[ ... \\]
En Fonction de k :
\\[ C(2^k)= 2^kC(2^{k-k}) + kf(2^{k}) \\]
\\[ C(2^k)= 2^kC(1) + kf(2^{k}) \\]

---
# Tri fusion
## Le moyen cas
\\[ C(2^k)= 2^kC(1) + kf(2^{k}) \\]
Changement variable inverse (pour revenir à une notation avec n)
\\[ n=2^k  \\]
Il faut isoler le k
\\[ n=2^k \Leftrightarrow ln(n)=ln(2^k) \\]
\\[ n=2^k \Leftrightarrow ln(n)=k~ln(2) \\]
\\[ n=2^k \Leftrightarrow k= \frac{ln(n)}{ln(2)} \\]
\\[ n=2^k \Leftrightarrow k= n log (n) \\]
\\[ C(n)= n \times C(1)  + n log (n) \times f(n) \\]

.underV[O(n log n)]

---
# Tri fusion
## Le meilleur cas
- Relativement la même !
- L'ensemble doit systématiquement fusionner à Gauche et à Droite.
- Les deux moitiés auront toujours plus ou moins la même taille
- La profondeur de récursion atteindrait alors log(n) (on divise par deux à chaque fois !)
- On a bien une complexité de .underV[O(n log(n))]

---
# Tri fusion
## Le pire cas
.under[Bin la même]
<br>

On a bien une complexité de .underV[O(n log(n))]

---
# Tri fusion
## Autres exemples

---
# Tri fusion
## Autres exemples

---
# Do you wanna dance ?

---
# Bilan
- Il existe une multitude d'algorithmes de tris
- L'objectif n'est pas de trouver la complexité exacte MAIS
- Trouver le temps d'exécution et/ou de mémoire d'un algorithme
- .under[Pourquoi ?]
  - Résoudre des problèmes
  - Adapter un algorithme à son contexte d'exécution

---
# Un lien super sympa !
<a href="https://visualgo.net/en/sorting" target="_blank"> <img src="img/visualgo.png"  width=700/> </a>

---
# Autres liens
## Simulation
- <a href="https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/" target="_blank">hackerearth</a>
- <a href="https://opendsa-server.cs.vt.edu/embed/quicksortAV" target="_blank">opendsa-server</a>
- <a href="https://www.algostructure.com/sorting/quicksort.php" target="_blank">Algo structure</a>
- <a href="https://www.log2base2.com/algorithms/sorting/quick-sort.html" target="_blank">Log2base2</a>
- <a href="https://qkzk.xyz/docs/nsi/cours_terminale/algorithmique/diviser_pour_regner/tri_fusion/" target="_blank"> qkzk.xy </a>