[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?

[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.

[dwils098]

Post has been updated.

[coder007]

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