Quickselect Algorithm

[AlgoLover]

http://www.techiedelight.com/quickselect-algorithm/

[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 → dwils098]

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 → CarolineW]

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 → dwils098]

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

[dwils098 → coder007]

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 → dwils098]

I have emailed them. post should be updated soon.

[dwils098 → coder007]

Post has been updated.

[coder007 → dwils098]

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

[cristiancavalli]

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

[kough]

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

[coder007 → kough]

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

[kough → coder007]

Ah, missed that paragraph. Thanks.