2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It could be a typo. It would help if you copy their version of partition. $\endgroup$ – Yuval Filmus May 15 '14 at 14:49
  • $\begingroup$ @YuvalFilmus There you go. :) $\endgroup$ – Levi Botelho May 15 '14 at 15:24
  • $\begingroup$ I guess @Yuval asked for the partition algorithm that they are using, not the definition. Can you post that? $\endgroup$ – Sayan Bandyapadhyay May 15 '14 at 15:37
  • $\begingroup$ @SayanBandyapadhyay - Apologies. Done. $\endgroup$ – Levi Botelho May 15 '14 at 15:45
  • $\begingroup$ Is it really the case that step 2 scans for $\geq$ while step 3 scans for $\leq$? I would expect (think it is necessary for correctness of the algorithm) that one of those would not include the equality (either strictly greater or strictly less.) $\endgroup$ – Wandering Logic May 15 '14 at 17:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's not completely clear from the informal defintion the OP gave, but I think that you do not compare 1 with pivot, you start at 2 and loop until you find something else that is < pivot. (The reason I believe this is that you need the pivot not to have moved in order to perform the exchange of the pivot in the last step.) $\endgroup$ – Wandering Logic May 15 '14 at 17:05
  • 1
    $\begingroup$ The informal definition OP gave clearly says that you need to compare 1 with pivot as we want an element greater than or equal to pivot. Actually here you must need to do that. If you skip that comparison then at last you need to swap pivot with the element where left and right pointer meet, or, the pivot will not come to its actual position in sorted array. As, in this version of partition the authors are not doing that you need to compare pivot with first element. The main thing is to say that the book doesn't say it wrong. The version they have defined actually needs $N+1$ comparisons. $\endgroup$ – Sayan Bandyapadhyay May 15 '14 at 17:19

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.