Quick Sort - First Element As Pivot

Question

I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot (15) into its appropriate position.

Example: [15, -7, 22, 7, 21, 34, -13, 19]

My understanding:

15, -7, 22, 7, 34, -13, 19
#   ^                   ^

Move left-pointer to first element larger than the pivot. 1 comparison (move to 22). Move right-pointer to first element smaller than the pivot. 1 comparison (move to -13).

15, -7, 22, 7, 34, -13, 19
#       ^           ^

Swap elements at the pointers (22, -13).

15, -7, -13, 7, 34, 22, -13, 19
#       ^           ^

Move left-pointer to first element larger than the pivot. 2 comparisons (move to 34). Unable to move right-pointer to first element smaller than the pivot (cannot past the left-pointer.

15, -7, -13, 7, 34, 22, -13, 19
#               ^   ^

Swap elements at the pointers (34, 22).

15, -7, -13, 7, 22, 34, -13, 19
#               ^   ^

This is where I am stuck. My understanding is that the pivot should then be swapped with 22, but that doesn't seem correct?

How do I move the pivot (15) into its appropriate position?

Answer 1

Usually, a random pivot is selected and moved to the first location. After swapping -13 and 22, your pointers should be on 7 and 34.

7 and 34 are correctly placed. Also 7 and 34 are adjacent, so time has come to put the pivot in its correct place.

array looks like this

15, -7, -13, 7, 34, 22, 19

So now you know that all elements after 34 are greater than 15. So swap the first element before 34 with the pivot.

So array looks like

7, -7, -13, 15, 34, 22, 19

Now all on left of 15 are lesser than 15 and all on right of 15 are greater than 15