13
votes
Sorting sequence with $O(n^{\frac{3}{2}})$ inversions
You can't sort it in linear time.
Suppose you have $n$ items, and you divide them into $\sqrt{n}$ consecutive blocks of $\sqrt{n}$ items each.
You need to take $\sqrt{n} \log \sqrt{n}$ comparisons ...
- 24.3k
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, ...
- 9,595
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 ...
- 9,595
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 ...
- 8,896
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,772
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,733
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
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,367
8
votes
Sorting sequence with $O(n^{\frac{3}{2}})$ inversions
This is a topic of "adaptive sorting." As a starter, see the wikipedia page https://en.wikipedia.org/wiki/Adaptive_sort .
It is known that we can sort a sequence of length $n$ with $k$ inversions ...
- 3,726
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
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,537
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,475
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.1k
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,758
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,531
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
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.1k
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 ...
- 11.7k
3
votes
Accepted
Quicksort: compute the expected number of comparisons as a function of $M$ and $t$
I got a reply from the problem author, wanted to post the info here for reference:
Apparently the problem was solved by Pascal Hennequin in his PhD thesis. Chern and Hwang discuss the solution in ...
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
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 ...
- 36.9k
2
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 ...
- 8,896
2
votes
Patience Sort+ ping pong merge implementation
I hope I understood correctly how the ping-pong merge worked. If so here is why it uses two arrays:
A typical merge operations takes two runs in an array and merges them in another arra; then, it ...
- 121
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,631
1
vote
Selecting unique records from a large dataframe with many duplicate records
In the context of Theoretical Computer Science, there are various strategies to (quickly) select the unique elements of a list, mainly comparison based and value based.
Value based: If computing a ...
- 2,733
Only top scored, non community-wiki answers of a minimum length are eligible