Questions tagged [selection]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
136 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 ...
14
votes
0answers
402 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 ...
0
votes
0answers
810 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_{...
4
votes
1answer
29k 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 ...
25
votes
2answers
3k 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 ...