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