cours_7.md

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 (2/3)

Exercice: Proposer un algorithme

. . .

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:

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

Tri rapide ou quicksort (5/8)

Deux variables sont primordiales:

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

Pseudocode: quicksort

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

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

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

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 à bulle (3/N)

Exercice: écrire l'algorithme du tri à bulles

. . .