Skip to main content
Wikipedia uses a slightly different version of the algorithm
Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

You haveYou've misunderstood the algorithm and it doesn't have the behaviour you suggest. It

Let the pivot value be $p$. The algorithm searches from the left of the array for something bigger than the pivota value $\ell\geq p$ and from the right of the array for something less than the pivota value $r\leq p$. It then only exchangesswaps them if it finds two values of that formthey're in the wrong order relative to each other, i. As suche., if $\ell>r$, so it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.

You have misunderstood the algorithm. It searches from the left of the array for something bigger than the pivot and from the right of the array for something less than the pivot. It only exchanges if it finds two values of that form. As such, it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.

You've misunderstood the algorithm and it doesn't have the behaviour you suggest.

Let the pivot value be $p$. The algorithm searches from the left for a value $\ell\geq p$ and from the right for a value $r\leq p$. It then only swaps them if they're in the wrong order relative to each other, i.e., if $\ell>r$, so it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.

Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

You have misunderstood the algorithm. It searches from the left of the array for something bigger than the pivot and from the right of the array for something less than the pivot. It only exchanges if it finds two values of that form. As such, it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.