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

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

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

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

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

## Exemple

![Tri à bulles d'un tableau d'entiers](figs/tri_bulles.svg)


# Tri à bulle (3/N)

## Exercice: écrire l'algorithme du tri à bulles

. . .