Quicksort - Problème d'identification pivot

Question

Je suis en train de comprendre quicksort et je reçois l'idée générale, mais je vais avoir du mal à la question ci-dessous. Existe-t-il un moyen facile d'identifier quel pivot est utilisé en fonction du tableau après chaque itération?

Consider the following array and its state after iterations of QuickSort on the array: 

Initial Array: 32, 12, 17, 73, 40, 88, 16, 75 
After Iter 1: 32, 12, 17, 40, 16, 73, 88, 75 
After Iter 2: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 3: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 4: 12, 16, 17, 32, 40, 73, 88, 75 
After Iter 5: 12, 16, 17, 32, 40, 73, 75, 88 

Nom de la stratégie de sélection de pivot utilisée dans cette exécution QuickSort.

Conseil: Examiner ce que la valeur est sélectionnée en tant que pivot à chaque étape. Rappelez-vous que QuickSort trie d'abord le sous-ensemble gauche et sa gauche sous-ensemble récursive avant trier les bons sous-réseaux.

Answer 1

Tout élément est choisi comme pivot, puis dans la première itération, tous les éléments plus petits que pivot sont placés à gauche du pivot et plus à droite, si elles ne sont pas déjà. Cela signifie que le pivotement du pivot vers l'avant dans le tableau est également nécessaire. Sachant cela et en regardant l'itération devrait aider à identifier le pivot.

Par exemple. Dans le cas ci-dessus, je crois que l'élément central est choisi comme pivot, c'est-à-dire 73. Après la première itération, tous les éléments inférieurs sont déplacés vers la gauche et plus grands que vers la droite.