# Tag Info

24

Preprocess the array of $n$ values in time $O(n)$: $i\leftarrow n$ while $i>2$ Compute the median $m$ of $A[1..i]$ in time $O(i)$ partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time. $i \leftarrow \lfloor i/2 \rfloor$ The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$ Answer a query for the $k$ ...

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

14

Assume for simplicity that $n = 2^m$. Use the linear time selection algorithm to find the elements at positions $2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given $k$, find $t$ such that $2^{t-1} \leq k \leq 2^t$; note that $2^t \leq 2k$. Filter out all elements of rank at most $2^t$, and now use the linear time selection algorithm to find the ...

13

Goodrich's "Randomized Shellsort: A Simple Oblivious Sorting Algorithm" has a discussion of data-oblivious sorting. Sorting networks are data-oblivious, but impractical in general, as I understand it.

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

10

We can compute $m$ in linear time. For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$. We want to compute $m = \max_i B[i]+i$. Let $max = \max_i A[i]$. Obviously $max \leq m$. Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq ...

9

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec Divide the vertices into two groups - some will represent literals, the ...

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

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

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

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

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

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

Yes there is. The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004. The best known randomized algorithm in linear space runs in time within $O(n\sqrt{\lg\lg n})$ and was presented by Han and Thorup in 2012. For more details, see the section on "Trans-dichotomous algorithms" from the ...

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

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

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

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

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

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

As I was told by Abhishek Methuku, this has been studied already, in fact several times, see e.g. http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter For $k$ large, the answer is close to $n \log_{k!}(n)$ but e.g. $k=3$ seems to be open.

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

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

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