Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Given a sequence of elements, find a permutation such that the elements are in a certain order.

4
votes
0answers
68 views

Asymptotic complexity of mass production

For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1). Let $k{\times}f : \{0,1\}...
10
votes
1answer
265 views

Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons? Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but ...
3
votes
0answers
39 views

Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
5
votes
3answers
433 views

Sorting a programs instructions until it works

Lets say I have a computer program below. (define (factorial x) (if (= x 0) 1 (else (* x (factorial (- x 1))))) I then take each line of the ...
6
votes
1answer
146 views

Computing topological sort while keeping edges “short”

Motivation: I want to compute a topological sort order in which the connected vertices are close to each other. Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
-5
votes
1answer
72 views

Does any DAG can be topologically sorted? [closed]

I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. The key point is that before getting them into database, I need run "topological sort" in ...
12
votes
1answer
626 views

Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time $$O(n \sqrt{\log n}), $$ and linear space. The paper seems reasonable, though I am ...
4
votes
0answers
125 views

How fast can we sort a list if we know how it was written?

Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the ...
4
votes
1answer
117 views

Necessary and sufficient number of comparisons by every element to fully sort a set of n elements? [duplicate]

Given $n$ distinct elements. Is there a sorting algorithm which ensures that every element is compared atmost $\lg n$ time? Or is there a higher lower bound?
16
votes
1answer
902 views

“Almost sorting” integers in linear time

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
8
votes
1answer
133 views

Original reference for Huffman shaped Merge Sort?

What is the first publication of the concept of optimizing merge sort by identifying sequences of consecutive positions in increasing orders (aka runs) in linear time; then repeatedly merging the ...
11
votes
1answer
539 views

Enumerating topological sorts of a vertex-labeled DAG

Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
7
votes
2answers
161 views

Quick-select contiguous subarray

Motivated by the question from this blog post, the following data structure question seems interesting and fun to me. Preprocess: A list of numbers $A = a_1,...,a_n$ Query(s,t,k): Return the $k$-th ...
5
votes
1answer
244 views

Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at ...
2
votes
0answers
100 views

Quicksort optimal partition

Has the question been studied, how to find the shortest sequence of partition choices so that a quick-sort algorithm can sort a set? To be clear, I'm not interested in quick sort per se, but in ...
6
votes
0answers
210 views

Most efficient inplace merge algorithms (stable and unstable)

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
-1
votes
2answers
225 views

Sorting sequence with $O(n^{\frac{3}{2}})$ inversions

There is given sequence $a_1,...a_n$ such that there are $O(n^{\frac{3}{2}}) $ inversions in this sequence. I am thinking about sorting algorithm for that. I know lower bound for number of ...
11
votes
2answers
224 views

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

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
7
votes
1answer
194 views

Sorting using ring operations

Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time. Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done ...
2
votes
0answers
57 views

Are there any algorithms that are similar to Fagin's Algorithm, but for unranked lists?

Fagin's Algorithm is a popular algorithm for finding the top-$k$ items from multiple ranked lists of the items (i.e., via different scoring functions), using some monotonic aggregation function for ...
13
votes
2answers
2k views

Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
5
votes
1answer
223 views

Reducing sorting to max-flow

Is there a linear-time reduction from the sorting problem to the max-flow problem? If so, what would such a reduction look like?
16
votes
1answer
232 views

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

The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence ...
3
votes
0answers
166 views

Probabilistic sorting given pairwise comparison probability

Let $X = \{x_1, \dots, x_n\}$ be a set, and $f:[1..n]^2 \to [0, 1]$ be a function, such that $$f(i, j) \cdot f(j, k) \le f(i, k)$$ For all $1 \le i, j, k \le n$. Does there exist a randomized ...
11
votes
0answers
3k views

Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in restricted sorting problem: If we restrict sorting algorithms to use ...
13
votes
0answers
321 views

Is it possible to find the median with a linear size sorting network?

Is there a sorting network that makes only $O(n)$ comparisons and finds the median? The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
4
votes
1answer
136 views

How to Quantify Entropy in a Data Set

I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort ...
3
votes
1answer
107 views

Locally sorted sequences

Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$. Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | \...
4
votes
1answer
777 views

Is the bitonic sort algorithm stable?

I was wondering, is the bitonic sort algorithm stable? I searched the original paper, wikipedia and some tutorials, could not find it. It seems to me that it should be, as it is composed of merge / ...
1
vote
0answers
407 views

estimating the number of comparisons of Shell Sort

I would like to estimate the number of comparisons in ShellSort. I'm using $h_s = 2^s-1$, where $s=\left \lfloor{\log(n)}\right \rfloor, \left \lfloor{\log(n)}\right \rfloor -1, \dots, 1 $ ; I know ...
12
votes
1answer
387 views

Optimal randomized comparison sorting

So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to ...
0
votes
0answers
273 views

Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
4
votes
1answer
402 views

What's the difference between “adaptive sorting” and “sorting almost sorted data quickly”?

A SIGMOD 2014 paper from Microsoft Research states that the "importance of sorting almost sorted data quickly has just emerged over the last decade", and goes on to propose variants of Patience sort ...
6
votes
1answer
372 views

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

Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the ...
5
votes
1answer
313 views

Patience Sort+ ping pong merge implementation

A recent paper out of Microsoft Research describes a new, faster implementation of the patience sort algorithm. A key part of the implementation is an improved merging strategy dubbed the "ping-pong" ...
8
votes
1answer
213 views

Hierarchical sorting strategies for pattern-avoiding permutations?

For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \...
12
votes
2answers
443 views

Can we sort without permutations?

It is well-known that sorting permutations by transposition is in $\sf{P}$, as the minimum number of transpositions required to sort $\pi \in S_n$ is exactly $inv(\pi) = \{ (i,j) \in [n] \times [n] : ...
0
votes
1answer
239 views

How can I construct sorting network for $k$ numbers

How can I construct a sorting network for $k$ numbers? My goal is to implement sorting networks in Java for $k$ in the range $[3,\hspace{-0.03 in}32]$. To be even more specific, I only want to sort ...
4
votes
1answer
329 views

Heap with $O(1)$ delete-key

Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity). Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ ...
14
votes
2answers
1k views

Sorting using read-only stacks

Consider the following setting: we are given a stack $s$ which contains $n$ items. we can use a constant $O(1)$ number of extra stacks. we can apply the following operations on these stacks: check ...
12
votes
0answers
209 views

Hardness of optimal sorting

For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known. From a purely theoretical perspective, however, exactly optimal ...
0
votes
0answers
106 views

Is Ralf Hinze's Discriminator sort parallelizable?

According to this slide - the following sorting algorithms Merge Sort Insertion Sort Bubble Sort Quicksort Bogosort all rely on cmp - which has a fixed upper ...
4
votes
1answer
138 views

Compatible partial permutations

Please, correct my terminology as I am not a combinatorician (I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem. Let $P_k$ be ...
1
vote
1answer
182 views

Fast extraction of pairs overlapping an interval

I am trying to find a fast algorithm to extract pairs that overlap with a specified interval. Lets say I have a long list of pairs of integers, each pair (x1, x2) assuming x1 <= x2, (you can ...
9
votes
1answer
345 views

Complexity of blind sort?

We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean,...
11
votes
2answers
381 views

Linear time algorithm for finding shifted max

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct). Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} B[i]...
2
votes
1answer
223 views

Best Sorting for unlimited integer range

Is there a better than time $O(n\log n)$ and space $O(n)$ deterministic algorithm in the RAM model to sort $n$ positive integers whose range is unbounded? How about randomized?
15
votes
3answers
809 views

Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices ...
1
vote
2answers
307 views

algorithms to split data into roughly equal sized quantiles

What is the state-of-the art on algorithms that calculate/estimate approximate quantiles? I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having ...
5
votes
0answers
928 views

Minimum Number of Adjacent Swaps to Sort Numbers on a 2D Grid

Assume that we have $N$ numbers (labeled from $1$ to $N$) that are placed on a 1D (linear) array. For example, for $N=5$: If we want to sort these numbers with the minimum number of adjacent swaps (i....