Hot answers tagged

16 votes
Accepted

Would an optimal sorting network ever have to swap two numbers the "wrong" way

How do you decide what the "wrong way" is? Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn'...
user avatar
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 ...
user avatar
9 votes
Accepted

Locally sorted sequences

Your problem is solved in the paper Spheres of Permutations under the Infinity Norm — Permutations with limited displacement by Torleiv Kløve. See also A002524 and other sequences linked there. ...
user avatar
  • 14.1k
9 votes
Accepted

Reducing sorting to max-flow

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow ...
user avatar
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 ...
user avatar
  • 2,391
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 ...
user avatar
  • 5,712
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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 4,256
8 votes
Accepted

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

It seems not. Ian Parberry makes reference to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further ...
user avatar
7 votes
Accepted

Is the bitonic sort algorithm stable?

No, bitonic sort is not stable. For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$.
user avatar
  • 22.8k
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 #...
user avatar
  • 1,986
5 votes

Sorting using ring operations

This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible. I think you're ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,261
4 votes

Optimal randomized comparison sorting

Since your question is: "What is known?" Here's something: http://arxiv.org/abs/1307.3033 This gives an average case analysis of the Ford-Johnson Algorithm. The expected number of comparisons is $\...
user avatar
  • 551
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 ...
user avatar
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 ...
user avatar
  • 10.4k
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 ...
user avatar
  • 521
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 ...
user avatar
3 votes
Accepted

How to Quantify Entropy in a Data Set

Inversions are one way to measure "disorder" in a list: Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$. However,...
user avatar
2 votes

Determining what can be achieved by a permutation of elements of a noncommutative group

I show below that the $G$-test problem is NP-hard for some simple but infinite group $G$. The finite case is still open. proof Define the following functions: $f(x) = -x$ and $g_a(x) = x + a$. Then ...
user avatar
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 ...
user avatar
  • 121
2 votes

Hierarchical sorting strategies for pattern-avoiding permutations?

Another approach is enumerative encoding. Consider for example $231$-avoiding permutations, of which there are $C_n$. The number of $231$-avoiding permutations with $\pi^{-1}(n) = i$ is $C_{i-1} C_{n-...
user avatar
  • 14.1k
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....
user avatar
  • 112
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 ...
user avatar
  • 7,455
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible