Optimal column size for linear selection
1
Name:
Anonymous
2013-04-21 22:36
In CLRS, the linear selection algorithm based on the median of medians is given with sublist size 5. I remember seeing it (or something like it) a while ago in Knuth with size 7. The other day somebody claimed that the optimal sublist size was as close to sqrt(n) as possible, because efficiency increased as the sublist size did. It seems to me from some limited testing that that is absoute bullshit, but I can't find any place that does a strict analysis of which sublist size is the best. Pointers?
2
Name:
Anonymous 2013-04-21 22:56
3
Name:
Anonymous
2013-04-21 23:52
Yeah, wikipedia uses sublists of size 5 as well. They don't offer any justification for their choice of 5 though.
4
Name:
Anonymous
2013-04-22 10:26
faggot* 1_san = malloc(5 * sizeof(faggot))
5
Name:
Anonymous
2013-04-22 20:01
6
Name:
Anonymous
2013-04-22 20:09
7
Name:
Anonymous
2013-04-22 20:14
8
Name:
Anonymous
2013-04-22 20:19
9
Name:
Anonymous
2013-04-22 20:24
10
Name:
Anonymous
2013-04-22 20:29
11
Name:
Anonymous
2013-04-22 20:34
12
Name:
Anonymous
2013-04-22 20:40
13
Name:
Anonymous
2013-04-22 20:45
14
Name:
Anonymous
2013-04-22 20:50
15
Name:
Anonymous
2013-04-22 21:04
16
Name:
Anonymous
2013-04-22 21:10
17
Name:
Anonymous
2013-04-22 21:17