0
$\begingroup$

In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position.

The entry a[j] is in its final place in the array, for some j.

No entry in a[lo] through a[j-1] is greater than a[j].

No entry in a[j+1] through a[hi] is less than a[j].

And this comes from Algorithms, 4th Edition, as well:

First, we arbitrarily choose a[lo] to be the partitioning item—the one that will go into its final position.

Does the pivot go into its final position for all inputs without exception?

Improve this question
$\endgroup$
  • $\begingroup$ You are asking two independent questions; please restrict yourself to one per post here. I'm removing the second, you are welcome to repost. $\endgroup$ – Raphael♦ Jun 13 '15 at 10:56
  • $\begingroup$ @Raphael, I asked a new question about the bounds. $\endgroup$ – Maksim Dmitriev Jun 13 '15 at 11:13
2
$\begingroup$

The details depend on the partitioning method used, but usually the pivot ends up in its final position.

That follows from the second and third statement, by the way: all elements smaller than the pivot are to the left of it, and the larger to the right. The pivot is in between, and that is clearly its final position in the sorted array.

That the second and third statement hold is the central property of the partitioning method used.

Improve this answer
$\endgroup$
  • $\begingroup$ Why usually rather than always? $\endgroup$ – Maksim Dmitriev Jun 13 '15 at 11:15
  • $\begingroup$ @MaksimDmitriev I can't claim to know all partitioning schemes. In principle, you don't have to put the pivot there; you can also cover the whole array with recursive calls. Less efficient, but feasible. $\endgroup$ – Raphael♦ Jun 13 '15 at 13:32

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.