---
title: "Récursion et tris"
date: "2023-11-07"
header-includes: |
    \usepackage{xcolor}
---

# Exponentiation rapide ou indienne (1/4)

## But: Calculer $x^n$

* Quel est l'algorithmie le plus simple que vous pouvez imaginer?

. . .

```C
double pow(double x, int n) {
    if (0 == n) {
        return 1;
    }
    double p = c;
    for (int i = 1; i < n; ++i) {
        p = p * x; // x *= x
    }
    return x;
}
```

* Combien de multiplication et d'assignations en fonction de `n`?

. . .

* `n` assignations et `n` multiplications.

# Exponentiation rapide ou indienne (2/4)

* Proposez un algorithme naïf et récursif

. . .

```C
double pow(double x, int n) {
    if (n != 0) {
        return x * pow(x, n-1);
    } else {
        return 1;
    }
}
```

# Exponentiation rapide ou indienne (3/4)

## Exponentiation rapide ou indienne de $x^n$

* Écrivons $n=\sum_{i=0}^{d-1}b_i 2^i,\ b_i=\{0,1\}$ (écriture binaire sur $d$ bits, avec
$d\sim\log_2(n)$).
* 
$$
x^n={x^{2^0}}^{b_0}\cdot {x^{2^1}}^{b_1}\cdots {x^{2^{d-1}}}^{b_{d-1}}.
$$
* On a besoin de $d$ calculs pour les $x^{2^i}$.
* On a besoin de $d$ calculs pour évaluer les produits de tous les termes.

## Combien de calculs en terme de $n$?

. . .

* $n$ est représenté en binaire avec $d$ bits $\Rightarrow d\sim\log_2(n)$.
* il y a $2\log_2(n)\sim \log_2(n)$ calculs.

# Exponentiation rapide ou indienne (4/4)

## Le vrai algorithme

* Si n est pair: calculer $\left(x^{n/2}\cdot x^{n/2}\right)$,
* Si n est impair: calculer $x \cdot \left(x^{(n-1)/2}\right)^2=x\cdot x^{n-1}$.

## Exercice: écrire l'algorithme récursif correspondant

. . .

```C
double pow(double x, int n) {
    if (0 == n) {
        return 1;
    } else if (n % 2 == 0) {
        return pow(x, n / 2) * pow(x, n/2);
    } else {
        return x * pow(x, (n-1));
    }
}
```

# Tri par base (radix sort)

* N'utilise pas la notion de comparaisons, mais celle de classement successif dans des catégories (alvéoles).
* Pour simplifier
    * Tri de nombre entiers dans un tableau.
    * On considère que des nombres $\ge 0$ (sans perte de généralité).
    * On considère ensuite la représentation binaire de ces nombres.

# Principe de l'algorithme

1. On considère le bit le moins significatif.
2. On parcourt une 1ère fois le tableau et on place à la suite dans un 2ème tableau les éléments dont le bit est 0;
   puis on répète l'opération 2 pour les éléments dont le bit est 1.
3. On répète l'étape 2 en regardant le bit suivant et en permutant le rôle des deux tableaux.

On utilise donc deux tableaux pour réaliser ce tri.
A noter qu'à chaque étape, l'ordre des éléments dont le bit est à 0 (respectivement à 1) reste identique dans le 2ème tableau par rapport au 1er tableau.

# Illustration sur un exemple (1/6)

Soit la liste de nombre entier: 

|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|  5  | -5  |  1  |  6  |  4  |  -6 |  2  | -9  |  2  |

Le plus petit élément est -9. On commence donc par décaler les valeurs de 9.

|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 14  |  4  |  10 |  15 |  13 |  3  |  11 |  0  |  11 |

# Illustration sur un exemple (2/6)

* Écrivons les éléments en représentation binaire.
* La valeur maximale est 15, on a besoin de 4 bits.

|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 14  |  4  |  10 |  15 |  13 |  3  |  11 |  0  |  11 |
| 1110 | 0100 | 1010 | 1111 | 1101 | 0011 | 1011 | 0000 | 1011 |

# Illustration sur un exemple (3/6)

* On considère le bit de poids faible

|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 111**0** | 010**0** | 101**0** | 111**1** | 110**1** | 001**1** | 101**1** | 000**0** | 101**1** |

. . .

* On obtient le tableau:

|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 111\textcolor{red}{0} | 010\textcolor{red}{0} | 101\textcolor{red}{0} | 111\textcolor{green}{1} | 110\textcolor{green}{1} | 001\textcolor{green}{1} | 101\textcolor{green}{1} | 000\textcolor{red}{0} | 101\textcolor{green}{1} |
| \textcolor{red}{1110} | \textcolor{red}{0100} | \textcolor{red}{1010} | \textcolor{red}{0000} | \textcolor{green}{1111} | \textcolor{green}{1101} | \textcolor{green}{0011} | \textcolor{green}{1011} | \textcolor{green}{1011} |

# Illustration sur un exemple (4/6)

* On passe au 2ème bit et on obtient le tableau:

|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 11\textcolor{green}{1}0 | 01\textcolor{red}{0}0 | 10\textcolor{green}{1}0 | 00\textcolor{red}{0}0 | 11\textcolor{green}{1}1 | 11\textcolor{red}{0}1 | 00\textcolor{green}{1}1 | 10\textcolor{green}{1}1 | 10\textcolor{green}{1}1 |
| \textcolor{red}{0100} | \textcolor{red}{0000} | \textcolor{red}{1101} | \textcolor{green}{1110} | \textcolor{green}{1010} | \textcolor{green}{1111} | \textcolor{green}{0011} | \textcolor{green}{1011} | \textcolor{green}{1011} |

. . .

* On passe au 3ème bit et on obtient le tableau:

|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 0\textcolor{green}{1}00 | 0\textcolor{red}{0}00 | 1\textcolor{green}{1}01 | 1\textcolor{green}{1}10 | 1\textcolor{red}{0}10 | 1\textcolor{green}{1}11 | 0\textcolor{red}{0}11 | 1\textcolor{red}{0}11 | 1\textcolor{red}{0}11 |
| \textcolor{red}{0000} | \textcolor{red}{1010} | \textcolor{red}{0011} | \textcolor{red}{1011} | \textcolor{red}{1011} | \textcolor{green}{0100} | \textcolor{green}{1101} | \textcolor{green}{1110} | \textcolor{green}{1111} |


# Illustration sur un exemple (5/6)   

4. On passe au dernier bit et on obtient le tableau final:

|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| \textcolor{red}{0}000 | \textcolor{green}{1}010 | \textcolor{red}{0}011 | \textcolor{green}{1}011 | \textcolor{green}{1}011 | \textcolor{red}{0}100 | \textcolor{green}{1}101 | \textcolor{green}{1}110 | \textcolor{green}{1}111 |
| \textcolor{red}{0000} | \textcolor{red}{0011} | \textcolor{red}{0100} | \textcolor{green}{1010} | \textcolor{green}{1011} | \textcolor{green}{1011} | \textcolor{green}{1101} | \textcolor{green}{1110} | \textcolor{green}{1111} |

. . .

* En revenant à la représentation décimale, on a le tableau trié:

|  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|  0 |  3 |  4 | 10 | 11 | 11 | 13 | 14 | 15 |

# Illustration sur un exemple (6/6)   

* Pour revenir aux valeurs initiales, il faut décaler de 9 dans l'autre sens.

|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| -9  | -6  | -5  |  1  |  2  |  2  |  4  |  5  |  6  |

* Et alors?

. . .

* Et alors rien. C'est fini.


# Pseudo-code

```python
rien radix_sort(entier taille, entier tab[taille]):
# initialisation
    entier val_min = valeur_min(taille, tab)
    entier val_max = valeur_max(taille, tab)
    decaler(taille, tab, val_min)
    entier nb_bits = nombre_de_bits(val_max - val_min)
# algo
    entier tab_tmp[taille]
    pour pos de 0 à nb_bits:
        alveole_0(taille, tab, tab_tmp, pos) # 0 -> taille
        alveole_1(taille, tab, tab_tmp, pos) # taille -> 0
        echanger(tab, tab_tmp)
# post-traitement
    decaler(taille, tab, -val_min)
```
<!-- ```C
void radix_sort(int size,int tab[size]) {
   int val_min = tab[index_min(size,tab)];
   int val_max = tab[index_max(size,tab)];

   decaler(size, tab,val_min);
   int nb_bits = get_nb_bits(val_max-val_min);

   int tab_tmp[size];
   for (int pos=0;pos<nb_bits;pos++) {
      bucket_0(size,tab,tab_tmp,pos);
      bucket_1(size,tab,tab_tmp,pos);
      swap(tab,tab_tmp);
   }
   decaler(size,tab,-val_min);
}
``` -->

# Un peu plus de détails (1/2)

## La fonction `decaler()`

```python
rien decaler(entier taille, entier tab[taille], entier val):
    pour i de 0 à taille-1:
        taille[i] -= val
```

. . .

## La fonction `echanger()`

```python
rien echanger(entier tab[], entier tab2[])
# échanger les tableaux (sans copier les valeurs)
```

# Un peu plus de détails (2/2)

## La fonction `alveole_0()`

```python
rien alveole_0(entier taille, entier tab[taille], 
               entier tab_tmp[taille], entier pos):
    entier k = 0
    pour i de 0 à taille-1:
        si bit(tab[i], pos) == 0:
            tab_tmp[k] = tab[i]
            k = k + 1
```

. . .

## La fonction `alveole_1()`

```python
rien alveole_1(entier taille, entier tab[taille], 
               entier tab_tmp[taille], entier pos):
    # pareil que alveole_0 mais dans l'autre sens
```

# Tri par fusion (merge sort)

* Tri par comparaison.
* Idée: deux listes triées, sont fusionnées pour donner une liste triée plus longue.
* Itérativement, on trie d'abord les paires de nombres, puis les groupes de 4 nombres, ensuite de 8, et ainsi de suite jusqu'à obtenir un tableau trié. 
<!-- * On simplifie ici: le tableau a une longueur de puissance de 2. -->

<!-- Pour son implémentation, le tri par fusion nécessite d'utiliser une zone temporaire de stockage des données de taille égale à celle de la liste de nombres à trier. On considère le cas du tri d'une liste de nombres entiers stockés dans un tableau. -->

# Principe de l'algorithme

* Soit `taille` la taille du tableau à trier.
* Pour `i = 0` à `entier(log2(taille))-1`:
    * Fusion des paires de sous-tableaux successifs de taille `2**i` (ou moins pour l'extrémité)

. . .

* Remarques: 
    * Pour l'étape `i`, les sous-tableaux de taille `2**i` sont triés.
    * La dernière paire de sous-tableaux peut être incomplète (vide ou avec moins que `2**i` éléments).

# Exemple de tri par fusion

* Soit la liste de nombres entiers stockés dans un tableau de taille 9: 

|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|  5  | -5  |  1  | 6   |  4  |  -6 |  2  | -9  |  2  |

. . .

* Fusion des éléments successifs (ce qui revient à les mettre dans l'ordre):

| étape |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|   0   |  \textcolor{red}{5}  | \textcolor{green}{-5} |  \textcolor{red}{1}  | \textcolor{green}{6} |  \textcolor{red}{4}  | \textcolor{green}{-6} |  \textcolor{red}{2}  | \textcolor{green}{-9} |  \textcolor{red}{2}  |
|   1   | \textcolor{red}{-5}  |  \textcolor{red}{5}  | \textcolor{green}{1} | \textcolor{green}{6} |  \textcolor{red}{-6} |  \textcolor{red}{4}  | \textcolor{green}{-9} | \textcolor{green}{2} |  \textcolor{red}{2}  |
|   2   | \textcolor{red}{-5}  |  \textcolor{red}{1}  |  \textcolor{red}{5}  |  \textcolor{red}{6}  | \textcolor{green}{-9} | \textcolor{green}{-6} | \textcolor{green}{2}  | \textcolor{green}{4} |  \textcolor{red}{2}  |
|   3   | \textcolor{red}{-9}  |  \textcolor{red}{-6} | \textcolor{red}{-5}  |  \textcolor{red}{1}  |  \textcolor{red}{2}  |  \textcolor{red}{4}  |  \textcolor{red}{5}  |  \textcolor{red}{6}  | \textcolor{green}{2} |
|   4   | -9  |  -6 | -5  |  1  |  2  |  2  |  4  |  5  |  6  |


# Pseudo-code (autrement)

```python
rien tri_fusion(entier taille, entier tab[taille])
    entier tab_tmp[taille];
    entier nb_etapes = log_2(taille) + 1; 
    pour etape de 0 a nb_etapes - 1:
        entier gauche = 0;
        entier t_tranche = 2**etape;
        tant que (gauche < taille):
            fusion(
                tab[gauche..gauche+t_tranche-1], 
                tab[gauche+t_tranche..gauche+2*t_tranche-1],
                tab_tmp[gauche..gauche+2*t_tranche-1]);
            #bornes incluses
            gauche += 2*t_tranche;
        echanger(tab, tab_tmp);
```


# Algorithme de fusion possible

## Une idée?

. . .

* Parcourir les deux tableaux jusqu'à atteindre la fin d'un des deux
    * Comparer  l'élément courant des 2 tableaux
    * Écrire le plus petit élément dans le tableau résultat
    * Avancer de 1 dans les tableaux du plus petit élément et résultat
* Copier les éléments du tableau restant dans le tableau résultat

# La fonction de fusion (pseudo-code autrement)

\footnotesize

## Une idée?

. . .

```python
# hyp: tab_g et tab_d sont triés
rien fusion(entier tab_g[], entier tab_d[], entier res[]):
    entier g = taille(tab_g)
    entier d = taille(tab_d)
    entier i_g = 0, i_d = 0
    pour i = 0 à g + d:
        si i_g < g et i_d < d:
            si tab_g[i_g] < tab_d[i_d]:
                res[i] = tab_g[i_g]
                i_g = i_g + 1
            sinon:
                res[i] = tab_d[i_d]
                i_d = i_d + 1
        sinon si i_g < g:
            res[i] = tab_g[i_g]
            i_g = i_g + 1
        sinon si i_d < d:
            res[i] = tab_d[i_d]
            i_d = i_d + 1

```

<!-- ## Complexité
L'algorithme présenté précédemment nécessite un certain nombre d'opérations lié à la taille $N$ du tableau.

Il y a essentiellement $\log_2(N)$ étapes. 

A chaque étape, le tableau est parcouru une fois avec un nombre constant effectué pour chacune des cases du tableau. En effet, l'opération de fusion implique de ne parcourir qu'une seule fois chacun des deux tableaux qu'on fusionne dans un 3ème tableau.

Ainsi, la complexité du tri par fusion est $\mathcal{O}(N\cdot \log_2(N)$. -->

# Tri rapide ou quicksort (1/8)

## Idée: algorithme `diviser pour régner` (`divide-and-conquer`)

* Diviser: découper un problème en sous problèmes;
* Régner: résoudre les sous-problèmes (souvent récursivement);
* Combiner: à partir des sous problèmes résolu, calculer la solution.

## Le pivot

* Trouver le **pivot**, un élément qui divise le tableau en 2, tels que:
    1. Éléments à gauche sont **plus petits** que le pivot.
    2. Élements à droite sont **plus grands** que le pivot.

# Tri rapide ou quicksort (2/8)

## Algorithme `quicksort(tableau)`

1. Choisir le pivot et l'amener à sa place:
    * Les éléments à gauche sont plus petits que le pivot.
    * Les éléments à droite sont plus grand que le pivot.
2. `quicksort(tableau_gauche)` en omettant le pivot.
3. `quicksort(tableau_droite)` en omettant le pivot.
4. S'il y a moins de deux éléments dans le tableau, le tableau est trié.

. . .

Compris?

. . .

Non c'est normal, faisons un exemple.

# Tri rapide ou quicksort (3/8)

\footnotesize

Deux variables sont primordiales:

```C
entier ind_min, ind_max; // les indices min/max des tableaux à trier
```

![Un exemple de quicksort.](figs/quicksort.svg)

# Tri rapide ou quicksort (4/8)

\footnotesize

Deux variables sont primordiales:

```C
entier ind_min, ind_max; // les indices min/max des tableaux à trier
```

## Pseudocode: quicksort

```python
rien quicksort(entier tableau[], entier ind_min, entier ind_max)
    si (longueur(tab) > 1)
        ind_pivot = partition(tableau, ind_min, ind_max)
        si (longueur(tableau[ind_min:ind_pivot-1]) != 0)
            quicksort(tableau, ind_min, pivot_ind - 1)
        si (longueur(tableau[ind_pivot+1:ind_max-1]) != 0)
            quicksort(tableau, ind_pivot + 1, ind_max)
```

# Tri rapide ou quicksort (5/8)

\footnotesize

## Pseudocode: partition

```C
entier partition(entier tableau[], entier ind_min, entier ind_max)
    pivot = tableau[ind_max] // choix arbitraire
    i = ind_min
    j = ind_max-1
    tant que i < j:
        en remontant i trouver le premier élément > pivot
        en descendant j trouver le premier élément < pivot
        échanger(tableau[i], tableau[j])
        // les plus grands à droite
        // mettre les plus petits à gauche
    
    // on met le pivot "au milieu"
    échanger(tableau[i], tableau[ind_max])    
    retourne i // on retourne l'indice pivot
```

# Tri rapide ou quicksort (6/8)

## Exercice: implémenter les fonctions `quicksort` et `partition`

. . .

```C
void quicksort(int size, int array[size], int first, 
               int last) 
{
    if (first < last) {
        int midpoint = partition(size, array, first, last);
        if (first < midpoint - 1) {
            quicksort(size, array, first, midpoint - 1);
        }
        if (midpoint + 1 < last) {
            quicksort(size, array, midpoint + 1, last);
        }
    }
}
```


# Tri rapide ou quicksort (7/8)

\footnotesize

## Exercice: implémenter les fonctions `quicksort` et `partition`

```C 
int partition(int size, int array[size], int first, int last) {
    int pivot = array[last];
    int i = first - 1, j = last;
    do {
        do {
            i += 1;
        } while (array[i] < pivot && i < j);
        do {
            j -= 1;
        } while (array[j] > pivot && i < j);
        if (j > i) {
            swap(&array[i], &array[j]);
        }
    } while (j > i);
    swap(&array[i], &array[last]);
    return i;
}
```

<!-- # Tri rapide ou quicksort (8/8)

## Quelle est la complexité du tri rapide?

. . .

* Pire des cas plus: $\mathcal{O}(N^2)$
    * Quand le pivot sépare toujours le tableau de façon déséquilibrée ($N-1$
      éléments d'un côté $1$ de l'autre).
    * $N$ boucles et $N$ comparaisons $\Rightarrow N^2$.
* Meilleur des cas (toujours le meilleur pivot): $\mathcal{O}(N\cdot \log_2(N))$.
    * Chaque fois le tableau est séparé en $2$ parties égales.
    * On a $\log_2(N)$ partitions, et $N$ boucles $\Rightarrow N\cdot
      \log_2(N)$.
* En moyenne: $\mathcal{O}(N\cdot \log_2(N))$. -->

# L'algorithme à la main

## Exercice *sur papier*

* Trier par tri rapide le tableau `[5, -2, 1, 3, 10, 15, 7, 4]`

```C













```

