Questions tagged [selection]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer

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 ...
Geoffrey Irving's user avatar
14 votes
0 answers

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 ...
domotorp's user avatar
  • 13.9k
1 vote
0 answers

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_{...
Ivan's user avatar
  • 111
5 votes
1 answer

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 ...
Manolo's user avatar
  • 153
26 votes
2 answers

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 ...
Jeffε's user avatar
  • 23.1k