HN Explorer

14 comments

[ 5.2 ms ] story [ 33.3 ms ] thread
dwils098
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?

coder007
here, numbering starts from 0 same as std::nth_element
[deleted]
(comment deleted)
CarolineW
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.

dwils098
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."
coder007
it doesn't return the index, rather the element itself..
dwils098
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?

coder007
I have emailed them. post should be updated soon.
[deleted]
(comment deleted)
kough
No mention of median-of-medians for pivot selection? Someone needs to re-read CLRS...
coder007
They have mentioned Introselect which is a hybrid of quickselect and median of medians.
kough
Ah, missed that paragraph. Thanks.