Algorithmique de Tri

Objectifs
  • Connaître les principaux algorithmes de tris d'entiers.
  • Savoir dérouler les algorithmes à la main sur des petits tableaux
  • Savoir produire le c/ de ces algorithmes
  • CConnaître et savoir calculer la complexité des tris

Ce chapitre traite exclusivement des algorithmes classiques de tri. La théorie sera exposée et appliquée sur des tableaux d’entiers (les algorithmes sont généralisables à n’importe quel type et critère de classement).

Enoncé du problème

On considère un tableau d’entier de taille N dont on veut trier les éléments de manière croissante. Une valeur peut être présente plusieurs fois dans le tableau. Ainsi:

11 -2 1515 42 2048 28 11 -78

devient, une fois trié:

-78 -2 11 11 28 42 1515 2048

On suppose l’existence d’une fonction echange / swap (voir chapitre précédent) qui permet de permuter dans un tableau t les cases d’indices i et j.

Tri Sélection

Le principe du tri sélection est le suivant:

  • on cherche le plus petit élément du tableau et on permute sa case avec la première (i.e. le plus petit élément se trouve en-tête)
  • on cherche le plus petit élément du sous-tableau [1, N-1] et on le permute avec la case d’indice 1.
  • … on répète ce processus jusqu’à ce que le tableau soit intégralement trié.

Algorithme

La procédure en C peut s’écrie comme:

// Rappel: on suppose l'existence de la fonction echange
void echange (int t[], int, int);

void tri_selection (int tab[], int N)
{
    for (int ideb = 0; ideb < N - 1; ideb++)
    {
        int imin = ideb;
        for (int i = ideb + 1; i < N; i++)
        {
            if (tab[i] < tab[imin]) imin = i;
        }
        echange (tab, ideb, imin);
    }
}

Complexité et invariant

Du point de vue du coût de l’algorithme en terme de comparaisons, on constate que lorsque ideb vaut 0, il y a (N-1) comparaisons, lorsque ideb vaut 1 il y a (N-2) comparaisons… et lorsque ideb vaut (N-2) il y a 1 comparaison. Au final le coût est (N-1) + (N-2) + ... + 1 = n \times (n-1) / 2 qui lorsque N est très grand tend asymptotiquement vers O(N^2).

On peut également déterminer l’invariant de ce tri (i.e. quantité qui ne varie pas entre chaque tour de boucle, c’est utile pour les preuves d’algorithme). Pour le tri sélection, l’invariant est le suivant: à la fin du tour ideb, le sous tableau t[0..ideb] contient les ideb+1 plus petits éléments du tableau et ce, dans l’ordre croissant de leurs valeurs.

Tri Insertion

Le principe du tri intérieur est celui qu’on utilise pour trier des cartes à jouer:

  • on trie les 2 premières cartes
  • on regarde la troisième carte et on l’insère à sa place (en décalant les cartes plus grandes vers la droite).
  • et on recommence jusqu’à ce que tout soit trié.

Algorithme

Le c/ est le suivant:

void tri_insertion (int tab[], int N)
{
    for (int i = 1; i < N; i++)
    {
        int current_element = tab[i];
        int insertion_index = i;

        while ((insertion_index >= 1) && (tab[insertion_index - 1] > current_element))
        {
            tab[insertion_index] = tab[insertion_index - 1];
            insertion_index--;
        }
        tab[insertion_index] = current_element;
    }
}

Complexité et invariant

La complexité de cette algorithme n’est pas aussi immédiate que précédemment. En effet dans la boucle while le nombre de comparaisons dépend de l’état initial du tableau (s’il est déjà trié ou non). En supposant que le tableau est trié, on remarque qu’il n’y a qu’une comparaison par tour de boucle, soit N-1 au total. A l’inverse si le tableau est trié par ordre décroissant, on aura 1 puis 2puis … puis N-2 comparaisons dans la boucle while. Ainsi la complexité est de O(N) dans le meilleur des cas et O(N^2) dans le pire des cas et en moyenne également.

L’invariant de ce tri est le suivant: au tour de boucle i, on insère l’élément t[i] dans le tableau t[0..i-1] déjà trié.

Tri Fusion

Le tri fusion utilise le principe de diviser pour régner. Pour cela il fonctionne de la manière suivante:

  • un tableau de taille 1 est forcément trié
  • on découpe le tableau initial en deux
  • on trie chacun des sous-tableaux (algorithme récursif)
  • on fusionne les deux sous-tableaux pour obtenir le tableau initial complètement trié.

Algorithme

L’algorithme est un peu plus complexe que les deux précédents et se base sur des procédures auxiliaires. La procédure principale est la suivante:

void tri_fusion (int tab[], int N)
{
    if (N > 1) fusion_recursive (tab, 0, N - 1);
}

puis on détaille le coeur du tri (découpage en deux sous-tableaux)

void fusion_recursive (int tab[], int premier, int dernier)
{
    if (premier < dernier)
    {
        int milieu = (premier + dernier) / 2;

        fusion_recursive (tab, premier, milieu);
        fusion_recursive (tab, milieu + 1, dernier);

        fusion (tab, premier, milieu, dernier);
    }
}

puis la fusion de deux sous-tableaux

int fusion (int tab[], int premier1, int dernier1, int dernier2)
{
    int premier2 = dernier1 + 1;
    int c2       = premier2;
    int c1       = premier1;
    int fusion[dernier2 - premier1 + 1];

    for (int i = 0; i < dernier2 - premier1 + 1; i++)
    {
        if ((c1 <= dernier1) && ((tab[c1] < tab[c2]) || (c2 > dernier2)))
        {
            fusion[i] = tab[c1];
            c1++;
        }
        else
        {
            fusion[i] = tab[c2];
            c2++;
        }
    }

    for (int i = 0; i < dernier2 - premier1 + 1; i++)
    {
        tab[premier1 + i] = fusion[i];
    }
}

Complexité

La complexité du tri-fusion se calcule comme suit: les comparaisons sont faites uniquement dans la fonction fusion (où il y a 3 comparaisons par tour de boucle). Pour trier le tableau complet:

  • on fusionne deux demi-tableaux triés soit environ 3 \times n comparaisons.
  • pour obtenir un demi tableau trié, on doit fusionner deux quart-tableaux triés soit encore une fois 3 \times n comparaisons (cf il y a deux demi-tableaux).
  • pour obtenir un quart-tableau trié, on doit fusionner deux ….

Au final il y a 3 \times n comparaisons par récursion avec en tout i récursions. i est tel que 2^i = N, soit i = ln_2(N). Ainsi la complexité asymptotique du tri-fusion est N \times ln_2(N).`

Récapitulatif

La section précédente a présenté 3 tris classiques, d’autres seront vus en TD et TP (tris à bulles et tri rapide).

Théorème relatif à la complexité
Un tri de tableaux d'entiers par comparaisons ne peut être réalisé en o(N x ln_2(N))</c/> en moyenne et dans le pire des cas. Un tri est optimal s'il a une complexité de Ω(N x ln_2(N))</c/>.

Ci-desssous figure un récapitulatif des complexités des principaux algorithmes de tri:

Algorithme Meilleur Moyenne Pire
Tri à bulles O(n) O(n^2) O(n^2)
Tri sélection O(n^2) O(n^2) O(n^2)
Tri insertion O(n) O(n^2) O(n^2)
Tri fusion O(n x ln_2(n)) O(n x ln_2(n)) O(n x ln_2(n))
Tri rapide O(n x ln_2(n)) O(n x ln_2(n)) O(n^2)

D’autres propriétés permettent de caractériser les algorithmes de tri:

  • stabilité: un algorithme de tri est stable si deux valeurs identiques restent dans le même ordre à la fin de l’algorithme
  • en place: un algorithme de tri est en place s’il trie sans créer de tableaux auxiliaires. Par exemple les tris insertion et sélection sont en place, le tri fusion ne l’est pas (complexité mémoire de O(n)).