Questions tagged [selection]
The selection tag has no usage guidance.
5
questions
3
votes
1
answer
144
views
Median finding with "green forests"?
I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but ...
- 3,243
14
votes
0
answers
511
views
Is it possible to find the median with a linear size sorting network?
Is there a sorting network that makes only $O(n)$ comparisons and finds the median?
The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
- 13.9k
1
vote
0
answers
1k
views
Efficient multi-selection algorithm
I have to implement an algorithm that solves the multi-selection problem.
The multiselection problem is:
Given a set S of n elements drawn from a linearly ordered set, and a set $K = {k_{1}, >k_{...
- 111
5
votes
1
answer
34k
views
tournament selection in genetic algorithms
I have a question about how to use a tournament selection in GA. Suppose that I have 100 individuals as an initial population and then I want to apply tournament selection for n generations, so I end ...
- 153
26
votes
2
answers
4k
views
Exact number of comparisons to compute the median
Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element ...
- 23.1k