Trie rapide

Quicksort est un algorithme de tri populaire et efficace qui utilise une approche de type "diviser pour régner". Il a été inventé par Tony Hoare en 1959. Cet algorithme une complexité temporelle moyenne de O(n log n) dans le meilleur et le moyen des cas, mais a une complexité temporelle dans le pire des cas de O(n^2) lorsque la liste d'entrée est déjà triée ou presque triée. Pour éviter ce scénario catastrophe, diverses techniques d'optimisation ont été mises au point, comme l'utilisation d'une sélection aléatoire du pivot ou le passage à un algorithme de tri différent pour les petites sous-listes.

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.

Le choix de l'élément pivot peut avoir un impact significatif sur les performances de l'algorithme. Idéalement, le pivot devrait être choisi de manière à diviser la liste d'entrée en deux sous-listes à peu près égales. On peut y parvenir en utilisant diverses stratégies de sélection du pivot, telles que la sélection de la médiane de trois éléments choisis au hasard ou l'utilisation de l'algorithme "médiane des médians" pour trouver l'élément médian de la liste.

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;
    }
}