13
votes
Accepted
Find odd-ranked numbers from a list
Lemma 1. Any comparison-based algorithm requires $\Omega(n\log n)$ comparisons in the worst case.
Proof sketch. Let $A$ be any comparison-based algorithm for the problem. Let $x=(x_1, x_2, \ldots, ...
- 10.9k
12
votes
Accepted
Number of permutations that satisfy a given set of comparisons
As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has.
This ...
- 9,697
12
votes
Accepted
Expected number of random comparisons needed to sort a list
This answer gives exact formulas for the expected number of steps, with and without replacement. To be clear, we interpret OP's problem as detailed in OP's Python gist: each step of the process makes ...
- 10.9k
11
votes
What is the fastest static comparison sort? What is the proper term for "static"?
The answer by Display name explains why the model trivializes. However, let me add some pointers to established terminology:
A query-based algorithm is called nonadaptive if all the oracle queries ...
- 18.2k
9
votes
Expected number of random comparisons needed to sort a list
I believe this takes $\Theta(n^2)$ oracle calls without replacement, and $\Theta(n^2\log n)$ oracle calls with replacement.
Lower bound: Assume my list has a single pair $x[i], x[i+1]$ out of order. ...
- 1,685
9
votes
Accepted
Computing topological sort while keeping edges "short"
Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.
It is NP-complete:
M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:
"Complexity Results for Bandwidth Minimization"
SIAM ...
- 5,782
9
votes
Accepted
Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons
Update: I expanded this answer into a paper Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons.
Yes, such an algorithm exists. I will only prove the $\mathrm{lg}(n!)+o(n)$ bound, but ...
- 2,587
9
votes
Accepted
Original reference for Huffman shaped Merge Sort?
I found the result hidden in an obscure 4p technical report: I share my results here in case others are interested.
Knuth mentions runs in his description of "natural merge sort" (page 160 of the ...
- 2,786
8
votes
Accepted
Quick-select contiguous subarray
$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.
- 4,509
8
votes
"Almost sorting" integers in linear time
This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:
https://www.inf.ethz.ch/personal/smilos/asort3.pdf
Unfortunately, the running time is not quite linear. The article ...
- 181
7
votes
What is the fastest static comparison sort? What is the proper term for "static"?
The reason this question isn't in the literature is because $m = \frac{n(n-1)}{2}.$ Suppose we know the order between every element except WLOG, between $\sigma(1)$ and $\sigma(2).$ It is impossible ...
- 299
6
votes
Accepted
Sorting a programs instructions until it works
This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$.
(Of course, that does not guarantee that you found the correct ...
- 4,485
6
votes
Accepted
Most efficient inplace merge algorithms (stable and unstable)
TLDR
The latest stable one with linear moves is from 2008 and with detailed description can be found here. According to their benchmarks, it is less than two times slower than standard merge that ...
- 76
6
votes
Expected number of random comparisons needed to sort a list
Not a complete answer, but here's a start.
Consider the index $p_{k} \in \{1,\dots n \}$ to represent the $k$th object in the series, with respect to order. We have:
$$x[p_{k}] < x[p_{j}] \...
- 161
6
votes
Accepted
Is sorting pairwise distances as hard as sorting arbitrary points?
This is an open question even for one-dimensional point sets. In this setting, the distance-sorting problem is equivalent to sorting X+Y, where $X$ is the input set and $Y=-X$.
- 23.2k
5
votes
Accepted
how to achieve a topological sort of an given sequence with minimum swaps
This problem is NP-complete. I will prove NP-hardness below
Source Problem
Colored Token Swapping on Cliques:
In the colored token swapping problem, we are given a graph with a colored token ...
- 2,883
5
votes
Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?
Based on Sasho Nikolov's very helpful comment, it seems that both papers use similar models of complexity which lead to unreasonable conclusions, such as the implication that any problem in PSPACE or #...
- 2,070
5
votes
Under what models do we know linear time sorting?
One obvious answer is "spaghetti sort", or in other words - sorting in a spaghetti model.
Intuitively, the spaghetti model says that your integers are given as lengths of (uncooked) spaghetti, and ...
- 5,616
4
votes
Quick-select contiguous subarray
When $k = \lceil (s-t)/2 \rceil$, this the range medians problem. There are solutions which are much better than the two trivial ones: you can answer the first $q$ queries in time $O(n\log q + q\log ...
- 18.2k
3
votes
Sorting a programs instructions until it works
Others have pointed out this is semidecidable. In most programming languages, the problem is NP-hard. In particular, the following problem is NP-hard:
Input: a set of lines of code
Question: does ...
- 12.3k
3
votes
Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?
Note that in a sorting network, the number of times an element is compared is bounded by the depth of the network. There are several simple sorting networks of depth $O((\log n)^2)$. The AKS network ...
- 556
3
votes
Accepted
"Almost sorting" integers in linear time
As it turns out, my question is quite irrelevant after all. Indeed, I am working on the RAM machine with uniform cost measure (i.e., we have registers whose registers are not necessarily of constant ...
- 9,697
3
votes
Lower bound for sorting without using a decision tree model
If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of ...
- 37.8k
3
votes
Is sorting NP-complete?
This is not a full answer, but some partial pieces of information (which you might already be aware of).
This is related to the number of linear extensions of the poset. It is known that the worst-...
- 881
2
votes
finding smallest k elements in array in O(k)
First use $O(n)$ to build a min-heap. It is known that we can use $O(k)$ to find the $k$ smallest elements in a min-heap:
Frederickson, Greg N., An optimal algorithm for selection in a min-heap, Inf....
- 112
2
votes
Accepted
Formally prove that the loops of this sorting algorithm will terminate
Since the loop variables $i$ and $j$ are not modified in the loop body, you can compute the exact number of iterations. The inner loop is executed $n-i$ times in each iteration of the outer loop, so ...
2
votes
Accepted
A sorting algorithm that uses the minimum comparasions possible
Using simple methods, it can be shown that any comparison-based algorithm must perform at least $n\log{n}-o(nlogn)$ comparisons. This bound is obtained (up to lower terms) by the binary insertion sort ...
2
votes
Lower bound for sorting without using a decision tree model
The paper "Sorting and Element Distinctness on One-Way Turing Machines" by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.
- 4,640
2
votes
Accepted
Can arbitrary comparator be transformed into equivalent key for radix sort?
does for every comparator C(key) exist a function M(key) such that sorting by C gives the same result as radix-sorting by the output of M?
SHORT ANSWER
Not for non discrete value domains, but yes for ...
- 2,786
2
votes
What is the fastest static comparison sort? What is the proper term for "static"?
Assume all array elements are different. If two items are consecutive in the sorted array, then they must be compared to each other, otherwise we cannot know which one should come first. And since we ...
- 127
Only top scored, non community-wiki answers of a minimum length are eligible