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.