Quickselect Algorithm
techiedelight.com
Quickselect Algorithm
1–10 of 15 posts
Re: Quickselect Algorithm
#2Input: 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?
Re: Quickselect Algorithm
#3Input: 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?
here, numbering starts from 0
same as std::nth_element
Re: Quickselect Algorithm
#4Input: 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]
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
This is deeply, deeply confusing. Badly expressed, and a very poor example.
Re: Quickselect Algorithm
#5Re: Quickselect Algorithm
#6Input: 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,…
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."
Re: Quickselect Algorithm
#7Earlier quoted context omitted.
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,…
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..
Re: Quickselect Algorithm
#8Earlier quoted context omitted.
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,…
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."
[deleted]
Re: Quickselect Algorithm
#9Earlier quoted context omitted.
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?
Re: Quickselect Algorithm
#10Earlier quoted context omitted.
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.