---
title: "Tris et backtracking"
date: "2021-11-12"
patat:
eval:
tai:
command: fish
fragment: false
replace: true
ccc:
command: fish
fragment: false
replace: true
images:
backend: auto
...
# Tri par insertion (1/3)
## But
* trier un tableau par ordre croissant
## Algorithme
Prendre un élément du tableau et le mettre à sa place parmis les éléments déjà
triés du tableau.
# Tri par insertion (2/3)
## Exercice: Proposer un algorithme
. . .
```C
void tri_insertion(int size, int tab[size]) {
for (int i = 1; i < size; i++) {
int pos = i;
int tmp = tab[i];
while (pos > 0 && tab[pos - 1] > tmp) {
tab[pos] = tab[pos - 1];
pos = pos - 1;
}
tab[pos] = tmp;
}
}
```
# Tri par insertion (3/3)
## Question: Quelle est la complexité?
. . .
* Parcous de tous les éléments (ordre $N$); placer (ordre $N$).
* Moyenne: $\mathcal{O}(N^2)$.
. . .
* Pire des cas, liste triée à l'envers: $\mathcal{O}(N^2)$,
* Meilleurs des cas, liste déjà triée: $\mathcal{O}(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. `quisort(tableau_gauche)` en omettant le pivot.
3. `quisort(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 (4/8)
Deux variables sont primordiales:
```C
int low, high; // les indices min/max des tableaux à trier
```
# Tri rapide ou quicksort (5/8)
Deux variables sont primordiales:
```C
int low, high; // les indices min/max des tableaux à trier
```
## Pseudocode: quicksort
```C
void quicksort(array, low, high) {
if (less than 2 elems) {
pivot_ind = partition(array, low, high);
if (something left of pivot)
quicksort(array, low, pivot_ind - 1);
if (something right of pivot)
quicksort(array, pivot_ind + 1, high);
}
}
```
# Tri rapide ou quicksort (6/8)
## Pseudocode: partition
```C
int partition(array, low, high) {
pivot = array[high]; // choix arbitraire
i = first - 1;
j = last;
while i < j {
en remontant i trouver le premier élément > pivot;
en descendant j trouver le premier élément < pivot;
swap(array[i], array[j]);
// les plus grands à droite
// mettre les plus petits à gauche
}
// on met le pivot "au milieu"
swap(array[i], array[pivot]);
return i; // on retourne l'indice pivot
}
```
# Tri rapide ou quicksort (7/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 (8/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++;
} while (array[i] < pivot && i < j);
do {
j--;
} 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 à bulle (1/4)
## Algorithme
* Parcours du tableau et comparaison des éléments consécutifs:
- Si deux éléments consécutifs ne sont pas dans l'ordre, ils sont échangés.
* On recommence depuis le début du tableau jusqu'à avoir plus d'échanges à
faire.
## Que peut-on dire sur le dernier élément du tableau après un parcours?
. . .
* Le plus grand élément est **à la fin** du tableau.
* Plus besoin de le traiter.
* A chaque parcours on s'arrête un élément plus tôt.
# Tri à bulle (2/4)
## Exemple
# Tri à bulle (3/4)
## Exercice: écrire l'algorithme (poster le résultat sur matrix)
. . .
```C
void bubble_sort(int size, int array[]) {
for i in [size-1, 1] {
sorted = true;
for j in [0, i-1] {
if (array[j] > array[j+1]) {
swap(array[j], array[j+1]);
sorted = false;
}
}
if (sorted) {
return;
}
}
}
```
# Tri à bulle (3/4)
## Quelle est la complexité du tri à bulles?
. . .
* Dans le meilleurs des cas:
* Le tableau est déjà trié: $\mathcal{O}(N)$ comparaisons.
* Dans le pire des cas, $N\cdot (N-1)/2\sim\mathcal{O}(N^2)$:
$$
\sum_{i=1}^{N-1}i\mbox{ comparaison et }3\sum_{i=1}^{N-1}i \mbox{ affectations
(swap)}\Rightarrow \mathcal{O}(N^2).
$$
* En moyenne, $\mathcal{O}(N^2)$ ($N^2/2$ comparaisons).
# L'algorithme du PPCM *récursif* (1/2)
## Rappel de l'algorithme
```C
// on cherche i*m == j*m (i,j aussi petits que possibles)
int ppcm(int m, int n) {
int mult_m = m, mult_n = n;
while (mult_m != mult_n) {
if (mult_m > mult_n) {
mult_n += n;
} else {
mult_m += m;
}
}
return mult_m;
}
```
. . .
## Écrire l'algorithme *récursif* du PPCM (matrix)
# L'algorithme du PPCM *récursif* (1/2)
```C
int ppcm(int mult_n, int mult_m, int n, int m) {
if (mult_n < mult_m) {
return ppcm(n + mult_n, mult_m, n, m);
} else if (mult_n > mult_m) {
return ppcm(mult_n, m + mult_m, n, m);
} else {
return mult_n;
}
}
```