All Questions
Tagged with sorting approximation
3
questions
0
votes
2
answers
279
views
find which two points an arbitrary point is nearest to
I have a line segment of connected points (a path in 2D), and a point $P$ that is not calculated based on this segment, although I can guarantee that the point will be placed along the path.
Based on ...
- 127
1
vote
1
answer
98
views
Can a comparison network obtain all the n! permutations of a vector?
I want to permute a vector using comparison networks. This is the only method I have at my disposal.
My original idea is to use a sorting network like Batcher or Bitonic. Basically I place my vector ...
- 175
2
votes
0
answers
88
views
On bounding the average cost of top-down merge sort
Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\...
