Tri par tas

Le tri consiste à réorganiser un tableau en tas afin de crée une vue de celui-ci en temps qu'arbre pour retrouver plus rapidement les valeurs, l'algorithme se décompose donc en deux étapes, la constitution du tas pour obtenir le maximum à la racine et tout ses fils également organisés on en déduis donc que (1) { ∀ i ∈ [0..N] ∧ ∀ j ∈ [2*i..N] | T[i] > T[j] } → { is_heap([0..N]) } puis le tri qui consiste à soustraire ce maximum (la racine) du tas au profit d'une feuille quelconque du n° N, le tas est alors réarranger jusqu’à N-1 à l'étape suivante ce seras donc N-2 et ainsi de suite. Heapsort utilise donc les propriétées des arbres binaire, on fait un “tamisage” qui permet de ranger les éléments dans la liste sous forme de tas en jouant avec les indices ...

Dans un premier temps, a chaque itération on prend le premier élément non traiter et on le fait remonté vers la racine tant que cette élément est supérieur à sont parent. Quand tout les éléments sont placés dans le tas, alors la racine représente nécessairement l’élément le plus grand de la liste

Dans un second temps on échange la racine (qui est le plus grand) avec le dernier éléments de la liste, il est alors à ça place définitive dans la liste et n'est plus traité. La racine deviens alors un éléments quelconque, que l'on fait descendre dans l'arbre jusqu’à ce que les indices de ces deux parent n’appartienne plus au tas non trié, ou que l’élément gauche et droite soit respectivement inférieur et supérieur sinon on continue a faire descendre l'élément

La complexité temporelle du tri de tas est de O(n log n) dans le cas moyen et le cas le plus défavorable, ce qui en fait l'un des algorithmes de tri les plus efficaces. Cependant, il présente un facteur constant important en raison des multiples passages sur les données d'entrée, ce qui le rend plus lent que certains autres algorithmes de tri pour les petits ensembles de données.

Le tri en tas présente l'avantage d'être un algorithme de tri sur place, ce qui signifie qu'il ne nécessite pas de mémoire supplémentaire au-delà de la liste d'entrée. Il est donc utile dans les situations où la mémoire est limitée ou lorsque les données d'entrée sont trop volumineuses pour tenir dans la mémoire.

Le tri

Puisque l'on récupère le maximum du tas et qu'il est permuté avec le n°y de l'itération n°y (y décroît de N vers 0) on peut déduire que :

  • (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 ;

le premier grandis tandis que le second diminue à chaque itération on en déduis donc que l'élément n°y correspond au maximum du tas et le minimum de la partie triée qui engendre l'axiome :

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

la racine n'est plus le maximum, il est alors réarranger avec la même procédure de départ de constitution du tas pour retrouver un tas :

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

finalement quand le tas est vide l'espace entier est affecté par (2) et donc le tableau est trié entièrement :

  • (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)

Ma méthode de constitution du tas et de suppression d'un élément du tas (la racine) sont identique, puisque le but final engendré est identique. Le principe est simple lors de la constitution du tas en partant de l'élément y=(size-1)/2 correspondant à la fin de la dernière étape ayant des feuilles, jusqu’à 0 , chaque élément y est alors descendu à la place d'un de ses fils s'il est < au maximum des deux à celui-ci. On en déduis donc :

  • (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)

Même implémentation que is_heap à la différence que is_subheap ne commence pas à l'index 0 mais à un index donné @e et vérifie 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 induit 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 true;
}