Implémentation de Quicksort pour gérer les doublons

Question

J'ai cette question de l'année écoulée basée sur le scénario suivant:

Lorsque la liste des éléments à tri contient de nombreuses valeurs en double, nous pouvons améliorer QuickSort en regroupant toutes les valeurs qui sont égales au pivot au milieu, puis nous sommes de façon récursive ces valeurs à gauche et ces valeurs à droite. Apporter les modifications nécessaires à la méthode de partition pour y parvenir.

Voici la mise en œuvre de Quicksort, écrite en Java. Je n'inclurai pas le code dans la page principale car il semble que ce site demande la description du pseudocode plutôt que du code réel, même si le code est très «simple».

En particulier, cette implémentation QuickSort est similaire à celle typique, mais choisit son pivot à gauche du tableau.

J'ai une compréhension de base de l'algorithme Quicksort basé sur le code réel, mais souvent je dois décomposer le code moi-même pour le comprendre. Chaque fois que on me donne des indices de pseudocode pour comprendre l'algorithme [et pour être honnête, je ne sais pas parfois si un indice est très évident ou plutôt implicite], je ne peux pas apprécier en quelque sorte la «magie» derrière le pseudocode.

Ma compréhension de cette implémentation de QuickSort est que le tableau doit être itéré pour faire 2 régions de valeurs faibles et élevées, tandis que nous décidons dynamiquement de l'endroit où mettre le pivot, appelez-le position X, qui dans cette implémentation est choisi pour être le élément le plus à gauche du tableau d'entrée. Si cette position X est décidée dynamiquement, comment «des éléments de groupe égaux à pivot» au milieu », et comment adhère-t-il exactement aux principes derrière l'algorithme typique?

Informez-moi si plus d'informations sont requises ou si le formatage de la question n'adhère pas aux normes ici.