search

jeffgerickson / algorithms

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

[Oops.]Quickselect bugs #159

Open zhangshaos opened 5 years ago

zhangshaos commented 5 years ago

Please verify that the error is present in the most recent revision before reporting. I have got the newest version of the book, but it seem to have not fixed that.

Chapter number or note title: [1.Recursion]

Page number: [page.36]

Error description: [error] The Quickselect use Parttion Algorithm to locate the kth smallest element(divide a array A into three parts: A[1...k-1](smaller than A[k]), A[k], A[k+1...]).But the A[k] is not the kth smallest element if there are some same elements in A[1...k-1]. e.g. A[1..k-1] = [-4,-4,-4], A[k]=[0], A[k+1...] = [1,2,3...]. And the A[k] is the second samllest element not 4th.

Suggested fix (if any): [fix]

echuber2 commented 5 years ago

Suggested fix: Could perhaps replace "kth smallest" with "kth ordinal/in order", or just make a note that it's the kth smallest item if the items are distinct, and to keep it in mind from then on. The string "th smallest" appears several other times in the book too.