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