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,838
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.6k
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
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,742
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,792
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
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
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,495
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.3k
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
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,636
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,913
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 ...
- 38.5k
3
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....
- 122
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.4k
3
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 ...
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,838
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
Determining what can be achieved by a permutation of elements of a noncommutative group
With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the ...
- 9,838
2
votes
Hierarchical sorting strategies for pattern-avoiding permutations?
This has been now resolved positively, up to an asymptotically optimal dependence on the pattern. See
Michal Opler: An Optimal Algorithm for Sorting Pattern-Avoiding Sequences. FOCS 2024: 689-699
...
- 21
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,765
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,816
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
1
vote
Sampling strategies for Quicksort
Sebastian Wyld from the University of Liverpool has been extensively working on the analysis of various versions of QuickSort: His 2016 thesis, "Dual-Pivot Quicksort and Beyond: Analysis of ...
- 2,816
Only top scored, non community-wiki answers of a minimum length are eligible