Tri par tas

Le tri par tas, également connu sous le nom de Heapsort, est un algorithme de tri efficace qui utilise les propriétés des arbres binaires pour réorganiser un tableau en un tas (heap) afin de faciliter la récupération des valeurs triées.

Étapes du tri par tas :

  1. Constitution du tas :
    • L'objectif est de réorganiser le tableau en un tas, où chaque nœud est supérieur à ses fils.
    • Cela signifie que pour tout indice i dans le tableau, on a : T[i] > T[2*i+1] et T[i] > T[2*i+2].
    • Cette propriété de tas est obtenue en effectuant un "tamisage" (heapify) sur le tableau, en partant des nœuds intermédiaires (à partir de N/2-1) jusqu'à la racine.
  2. Tri proprement dit :
    • Une fois le tas constitué, on peut extraire le maximum (la racine) et le placer à la fin du tableau.
    • Ensuite, on réarrange le tas en échangeant la racine avec le dernier élément du tas, puis on réduit la taille du tas de 1.
    • Ce processus est répété jusqu'à ce que le tableau soit complètement trié.

Ainsi, le tri par tas utilise les propriétés des arbres binaires pour organiser efficacement les éléments du tableau, permettant une récupération rapide des valeurs triées. Formellement (1) ∀ i ∈ [0..N] ∧ ∀ j ∈ [2*i..N] | T[i] > T[j] } → { is_heap([0..N]) }

Dans un premier temps, lors de chaque itération, le processus consiste à sélectionner le premier élément non encore traité et à le transposer vers la racine du tas, sous réserve qu'il soit supérieur à son parent. Une fois que tous les éléments sont intégrés dans le tas, il est établi que la racine représente de manière invariable l'élément le plus grand de la liste.

Dans un second temps, la racine, qui est le plus grand élément, est échangée avec le dernier élément de la liste, l'assignant ainsi à sa position finale dans la liste où il n'est plus sujet à manipulation. À ce stade, la racine devient un élément quelconque, qui est ensuite déplacé vers le bas dans l'arbre jusqu'à ce que ses indices parents ne fassent plus partie du tas non trié. Cette descente se poursuit également si les valeurs des éléments à gauche et à droite de la racine ne respectent pas les contraintes imposées par le tas.

L'algorithme de tri par tas démontre une complexité temporelle de O(n log n) dans les cas moyens et les pires, le positionnant ainsi parmi les méthodes de tri les plus efficientes. Toutefois, il présente un facteur constant significatif en raison des multiples manipulations sur les données d'entrée, ce qui le rend relativement plus lent que certains autres algorithmes de tri pour les ensembles de données de petite taille.

L'atout principal du tri par tas réside dans son caractère "sur place", indiquant qu'il n'exige pas de mémoire supplémentaire au-delà de la liste d'entrée. Par conséquent, il s'avère avantageux dans les contextes où les ressources mémoire sont limitées ou lorsque les données d'entrée sont trop volumineuses pour être intégralement stockées en mémoire.

Le tri

Étant donné que le maximum du tas est récupéré et permuté avec l'élément à l'indice y lors de l'itération y (avec y décroissant de N à 0), il est possible de déduire ce qui suit :

  • (2) ∀ i,j ∈ [y..N] | i<j ∧ T[i] < T[j]
  • [y..N] correspond à la partie triée
  • et [0..y[ qui correspond au tas

Il est à noter que la première partie s'accroît tandis que la seconde diminue à chaque itération. Par conséquent, il en résulte que l'élément à l'indice y représente le maximum du tas et le minimum de la partie triée, ce qui engendre l'axiome suivant :

  • (3) { max([0..y]) = min([y..N]) }

Après que la racine ne soit plus le maximum, elle est réarrangée selon la même procédure initiale pour former un tas :

  • (4) { is_heap([0..y]) }

Enfin, lorsque le tas est vide, tout l'espace est affecté conformément à l'équation (2), ce qui implique que le tableau est entièrement trié :

  • (5) { ∀ i ∈ [0..N[ , T[i] < T[i+1] }.
template<typename T>
inline void heapsort(T* array, int size) noexcept
{
    if(size < 2) return; // un tableau de taille < 2 est soit vide, soit un singleton ils sont donc trié

    T* virtualArray = array - 1;
    int virtualSize = size + 2;

    assert(virtualArray == array-1); // vérification affectation
    assert(virtualSize == size+2);    // toujours vrai en principe

    for(int i=((size-1)/2); i>=0; --i)
    {
        sieving(virtualArray, i+1, virtualSize-1);
        assert(std::is_subheap(virtualArray, i+1, virtualSize-1)); // (7)
    }

    assert(std::is_heap(array, array+size-1)); // (1)

    for(int i=size-1; i>0; --i)
    {
        swap(array[0], array[i]);
        sieving(virtualArray, 1, i + 1);

        assert(std::is_heap(array, array+i)); // (4)
        assert(std::max(array, array+i) == std::min(array+i, array+size)); // (3)
        assert(std::is_sorted(array+i, array+size)); // (2)
    }

    assert(std::is_sorted(array, array+size)); // (5)
}

La constitution du tas (sieving)

La méthode de création et de suppression d'éléments dans le tas demeure similaire, car elle vise le même objectif final. Son principe est simple : lors de la création du tas, en partant de l'élément y=(size-1)/2 , qui correspond à la fin de la dernière étape contenant des feuilles, et en descendant jusqu'à 0, chaque élément y est déplacé vers la position d'un de ses fils si celui-ci est inférieur au maximum des deux. Cette constatation nous conduit donc à conclure que :

  • (7) { is_subheap(T, y, N) ; }
  • on testera donc tout les arbres en bas *1 puis leurs parents *2 … etc
// bring @element to the end of the pipe if is < to his parent
template<typename T>
inline int sieving(T *array, int element, int max) noexcept
{
    // while a left child exists
    while((element<<1) < max)
    {
        int j = (element<<1);

        if(j+1 < max && array[j] < array[j+1])
            j++; // take right child

        if(array[element] < array[j])
        {
            swap(array[element], array[j]);
            element = j; // recursive hack for performance
        }
        else return element;
    }

    return element;
}

Vérification d'un « sous-tas » (is_subheap)

L'implémentation de is_subheap est similaire à celle de is_heap, à la différence que is_subheap ne démarre pas à l'index 0 mais à un index spécifié @e, tout en vérifiant l'assertion :

  • { ∀ j ∈ [2*e..2*(e+1)-1] | T[e] > T[j] }

et réitéré sur j jusqu’à ce que e ≥ N pour tester les sous-arbres induits par chaque élément :

  • ∈ [2*e..2*(e+1)-1]. Donc l'axiome (7).
template<typename T>
inline bool is_subheap(const T *data, int element, int size)
{
    int subspace = element<<1;
    int subspaceend = std::min(size, (element<<2)-1); // subspace(element+1)-1

    if(subspace >= size)
        return true;

    bool cmp = true; // all element of the subspace of @element must be <
    for(int i = subspace; i<subspaceend && cmp; ++i)
    {
        cmp &= data[element] > data[i];
        cmp &= is_subheap(data, i, size); // recursive check for all children
    }

    return cmp;
}