1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.