Trie rapide

Partionement et recherche du pivot :

L'algorithme de quicksort permet, grâce au calcul du pivot de ranger chaque élément plus petit à ça gauche et chaque élément plus grand à ça droite, donc tous les éléments à gauche sont strictement plus petit que les éléments situé a droite. Le calcule du pivot permute un élément k (le pivot) à la fin, et itéré via deux indices, un de départ(i), et un de fin(j), si deux éléments sont telque $i>j$ alors ils sont permutés et $j$ est décrémenté, cela jusqu’à ce que les deux indices ce rencontre, à la fin le dernier élément (le pivot) est permuté avec l'indices $j$ et est à ça place définitive.

template<typename T>
inline int parted(array_view<T> &data)
{
    int j = 0, last = data.size-1;
    int pivot = data.size/2;
    data.swap(last, pivot);

    for(int i = 0; i<last; ++i)
    {
        if(data[i] <= data[last])
        {
            data.swap(i, j);
            j++;
        }
    }

    data.swap(last, j);

    return j;
}

Le trie des partions :

Nous utilisons cette propriété afin de traiter sous partie (à gauche et a droite du pivot) comme étant deux nouveaux tableau différent a traiter d'indice $[0,k]$ et $[k+1,N]$, il sont alors empiler/dépilé au fur et a mesure du traitement, n’excèdent pas $N/2$ du tableau de départ. Ces nouveaux tableau sont géré par un array_view permettant de décaler le pointer de donné à traiter au sein du tableau d'origine pour le “ré-indicer” virtuellement de 0 à N, mais également de pouvoir géré la pile.

template<typename T>
inline void quicksort(T *data, int count, int maxdepth = 5)
{
    if(count <= 1)
      return;

    auto last = std::make_shared<array_view<T>>(nullptr, 0, 0);
    auto tmp = std::make_shared<array_view<T>>(data, 0, count);
    auto end = tmp;

    while(last != end)
    {
        if(tmp->size >= maxdepth)
        {
            int k = parted(*tmp);
            auto left = std::make_shared<array_view<T>>(tmp->ptr, 0, k);
            auto right = std::make_shared<array_view<T>>(tmp->ptr, k+1, tmp->size);
            // insert in next computation
            left->next = right;
            end->next = left;
            end = right;
        }
        else if(tmp->size > 0)
        {
            heapsort(tmp->ptr, tmp->size);
        }

        last = tmp;
        tmp = tmp->next;
    }
}