Cost of partitioning in quicksort

Question

I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple.

When talking about the complexity of quicksort, the book says that the cost of partitioning, measured in the number of compares, is equal to N + 1, where N is equal to the number of elements in the collection to sort. We are assuming here that we just choose the first element in the collection to serve as the partition.

My question is would the cost of partitioning not really be equal to N - 1? That is, that you choose an element to serve as the partition and you compare it with every other element in the array.

--

As requested, the partitioning process is defined as follows:

• The entry which will serve as partition is in its final place in the array.
• No entries in positions before the partition are greater than the partition value.
• No entries in positions after the partition are less than the partition value.

At this point I'm guessing it is in fact a typo...

--

The partitioning algorithm is outlined as follows

• Take the leftmost array element as the "partitioning item"
• Scan the array from the left until an element greater than or equal to the partitioning item is found
• Scan from the right until an entry less than or equal to the partitioning item is found
• When both a right and left item are found, exchange them
• Repeat until the scan indexes cross
• Once the scan indexes cross, exchange the partitioning item with the rightmost entry in the lower side of the array.

Note that the "cost" of the partitioning is being calculated in compares and not array accesses.

Answer 1

This is a pretty common version of partition and in this case you need N+1 comparisons.

For example consider an array containing ${1,2,\ldots,N}$.

Now, 1 is your pivot (partitioning item). pivot 1 is compared with first element 1 and it is greater than or equal it, so you got the left item. Here you need 1 comparison.

Then, pivot 1 is compared with $N,N-1,\ldots$. Note that the right item will be 1 as we want a number less than or equal to the pivot. Hence you need to compare 1 with all the elements $N,N-1,\ldots,1$. Thus here you need $N$ comparisons.

In total you need $N+1$ comparison.

In general we have two pointers one from left and one from right. pivot is compared with elements pointed by these two pointers. Left pointers moves towards right, right pointer moves towards left. Thus all the elements are compared with pivot at least once. But, one element is compared twice where the two pointers meet and cross. Thus we need $N+1$ comparisons.