3 ms·
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 i
by CarolineW 10y ago
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 10y agoContext 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 10y agoit doesn't return the index, rather the element itself..
- dwils098 10y agoTrue. 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?
- deleted 10y ago[deleted]