Hot answers tagged

16

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't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit. Now, you can keep doing this until you've ...


13

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 to sort each one. And there are $\sqrt{n}$ of them, giving $\theta(n \log n)$ time total. And it's easy to see that there can't be more than $n^{3/2}$ ...


9

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. I found Kløve's paper by calculating the first few values of A002524 and finding it on the OEIS.


9

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 problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are ...


9

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 tome 3 of the 3rd edition), but he analyzes its complexity only on average (which yields n/2 runs), not in function of the number ρ of runs in 1985, Mannila proved ...


9

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 Journal on Applied Mathematics 34, (1978), pp. 477-495 It is problem [GT41] in the NP-completeness book by Garey and Johnson. The special case where every ...


8

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 above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n*log (\nu(n))$ (assuming $\nu(n) < n$)....


8

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 with $O(n \log (2+k/n))$ comparisons. When $k=O(n^{3/2})$, this translates to $O(n \log n)$. We also have a lower bound of $\Omega(n \log (2+k/n))$. Thus, we know ...


8

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.


8

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 deduce that the problem of verifying a sorting network is $co$-$NP$ complete. I can't find the original paper right away, but certainly it matches (my) ...


7

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 ; to mark the initial position. Comparison-exchanges are denoted by arrows where the head points at the desired location of the greater value. As written in the link that @JukkaSuomela posted a stable ...


7

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 under a likely randomization assumption we also get $\mathrm{lg}(n!)+O(n^{1-ε})$. I will also describe an attempt for $n^{0.5+o(1)}$ and $O(n^{0.5-ε})$. We can ...


6

I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to this wikipedia entry we can define it as follows. Let $X$ be a group, and let $H$ denote the set of tuples $(x_1,\ldots,x_n) \in X^n$ such that $x_1 \ldots x_n = 1_X$. If we let $G$ be the braid group $B_n$ generated by the moves $\sigma_i$, we can ...


6

This is a standard geometric data structure problem, which can be solved by storing the intervals $(x_1, y_1), \dots, (x_n, y_n)$ in an interval tree. Then you can extract all the intervals $(x_i,y_i)$ overlapping a given query interval $(X,Y)$ in $O(\log n + k)$ time, where $k$ is the number of output intervals.


6

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 permutation for input 5.) Specific running time estimates may depend on the programming language being used. For instance, in BASIC each line is supposed to start ...


6

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$.


5

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 going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory ...


5

No, such an algorithm cannot exist. Assume $t$ comparisons per element are allowed. For a start, consider the situation of merging two lists, one of size one, and the other of size $2^t$. There are $2^t+1$ possible results, and an easy adversarial argument shows that the element in the small list needs to participate in $t+1$ comparisons, and this element ...


5

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 #P can be solved in polynomial time. I welcome any comments which may lead to a modification of this tentative answer.


5

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 placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on ...


5

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 you sort them by placing them on a table, and then lowering your hand until you hit the tallest spaghetto (for spaghetto is the singular of spaghetti). You take ...


4

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 $\log n! +cn$ for a surprisingly small constant $c$ (about .05).


4

The following paper by Mark Jerrum studied the problem you mentioned when $G=H=S_n$ and $G=H=A_n$ (the alternating group): Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985) http://dx.doi.org/10.1016/0304-3975(85)90047-7 . Among other results, he proved that when $G=H=S_n$ and $\Gamma$ is the ...


4

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 n)$. I believe the algorithms can be adapted to arbitrary rank. References: paper that defined the problem best known algorithm an improvement for $q = \Omega(...


3

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 Transitional behaviors of the average cost of quicksort with median-of-(2t+1). I also found that googling quicksort "2t+1" yields the above paper :).


3

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, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly: An integer function on a permutation $\...


3

there is some research angle here dating at least to Knuth's Art of Computer Programming and presumably earlier in finding optimal sorting networks for low $n$. its intractable to find optimal sorting networks for small $n$ but it has been done up to about $n=10$ eg as in this recent notable paper, also using SAT. details about how to reduce the problem to ...


3

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 has a depth of $O(\log n)$ with a huge constant (according to Wikipedia).


3

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 there exist a permutation, so that this yields a syntactically valid program? If the programming language has two kinds of matched parentheses (e.g., () and []),...


2

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. Comput. 104, No. 2, 197-214 (1993). ZBL0818.68065..


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