search

jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

[Oops.] quicksort algorithm error #158

Closed saltycorn closed 5 years ago

saltycorn commented 5 years ago

Please verify that the error is present in the most recent revision before reporting.

Chapter number or note title: [title] Quicksort Page number: [page] page 29.

Error description: [error] In the for loop of the Quicksort partition code, shouldn't the update to l be after the swap? Suggested fix (if any): [fix] ^^

echuber2 commented 5 years ago

It seems fine to me... Note that in this book, Prof. Erickson uses 1-based indexing, not 0-based indexing. So suppose that the first item, A[1], is smaller than the pivot A[n]. Then l is increased from 0 to 1, and swap A[l] <-> A[i]where l and i are both 1. This correctly leaves the first element where it began.

jeffgerickson commented 5 years ago

The algorithm is correct as is.

If A[i] < A[n], then we've found a new item A[i] that is less than the pivot, so we increment the variable ℓ that stores the number of items less than the pivot, and then we swap A[i] with A[ℓ], so that all items in A[1..ℓ] are ℓess than the pivot, as required by the loop invariant. See the correctness proof at the bottom of the page.