Quickselect Algorithm | Hacker News Reader

Quickselect Algorithm

techiedelight.com

43 pointsAlgoLover12 comments

Input: arr = [7, 4, 6, 3, 9, 1] k = 2

Output: k’th smallest element in the array is 4

Am I missing something... shouldn't the k'th smallest element in this array be 3, given that k=2?

Sort the array:

  L = [7, 4, 6, 3, 9, 1]

  -> L = [1, 3, 4, 6, 7, 9]

Now L[k] = L[2] = 4.

The notation is potentially misleading, but consistent with this interpretation.

EDIT:

Ah, I was completely wrong.

  List : [7, 4, 6, 3, 9, 1]
  Index:  1  2  3  4  5  6

The smallest element is 1, the second smallest element is 3, the index of the second smallest element counting from 1 is 4.

This is deeply, deeply confusing. Badly expressed, and a very poor example.

Context can be clarified by writing: "Quickselect is a selection algorithm to find the INDEX OF THE kth smallest element in an unordered list. It is closely related to the quicksort sorting algorithm."

it doesn't return the index, rather the element itself..

True. This is what I meant by confusing, without properly defining the variables at play, in this context, k is the index of the element of the ordered list, and not the kth smallest element.

Semantics, I agree, but confusing nonetheless.

Or in other words, how do we define k?

I have emailed them. post should be updated soon.

Post has been updated.

here, numbering starts from 0 same as std::nth_element

A JS implementation for fun [tests-not-yet-implemented]: https://github.com/cristiancavalli/quick-select

No mention of median-of-medians for pivot selection? Someone needs to re-read CLRS...

They have mentioned Introselect which is a hybrid of quickselect and median of medians.

Ah, missed that paragraph. Thanks.

Reply on news.ycombinator.com