---
title: "Tris"
date: "2021-11-10"
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 d'un tableau d'entiers](figs/tri_insertion.svg)

# Tri par insertion (2/3)

## Exercice: Proposer un algorithme

. . .

```C
void tri_insertion(int N, int tab[N]) {
    for (int i = 1; i < N; i++) {
        int tmp = tab[i];
        int pos = 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é?

. . .

* Parcours de tous les éléments ($N-1$ passages dans la boucle)
    * Placer: en moyenne $i$ comparaisons et affectations à l'étape $i$
* 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)$

# L'algorithme à la main

## Exercice *sur papier*

* Trier par insertion le tableau `[5, -2, 1, 3, 10]`

```C













```

# 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)

Deux variables sont primordiales:

```C
int low, high; // les indices min/max des tableaux à trier
```

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

# Tri rapide ou quicksort (4/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 (more than 1 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 (5/8)

## Pseudocode: partition

```C
int partition(array, low, high) {
    pivot = array[high]; // choix arbitraire
    i = low;
    j = high-1;
    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 (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);
        }
    }
}
```

# L'algorithme à la main

## Exercice *sur papier*

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

```C













```



# 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++;
        } 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 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))$.



# 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 à bulles d'un tableau d'entiers](figs/tri_bulles.svg)


# 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 (4/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 à la main

## Exercice *sur papier*

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

```C













```


