Sto leggendo su quicksort, guardando diverse implementazioni e sto cercando di avvolgere la mia mente attorno a qualcosa.Quicksort: posizione di rotazione dopo una partizione
In this attuazione (che di opere corso), il perno viene scelto come elemento centrale e quindi il puntatore di spostamento destra e sinistra a destra e sinistra di conseguenza, scambiando elementi di partizionare attorno al perno.
Stavo provando l'array [4, 3, 2, 6, 8, 1, 0].
Sulla prima partizione, pivot è 6 e tutti gli elementi di sinistra sono già più piccoli di 6, quindi il puntatore a sinistra si fermerà al pivot. Sul lato destro, scambiamo 0 con 6, quindi 1 e 8, quindi alla fine della prima iterazione, la matrice sarà simile a:
[4, 3, 2, 0, 1, 8, 6].
Tuttavia, avevo l'impressione che dopo ogni iterazione in quicksort, il pivot finisse nella sua giusta posizione, quindi qui dovrebbe finire nella posizione 5 dell'array.
Quindi, è possibile (e ok) che il pivot non finisca nella sua iterazione corretta o è qualcosa di ovvio che mi manca?
Grazie per l'approfondita redazione, ha reso molto più chiaro. – kenny