Questions tagged [sorting]

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

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
14
votes
0answers
372 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 ...
12
votes
0answers
234 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 ...
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 ...
11
votes
1answer
694 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 ...
8
votes
0answers
249 views

For median is it optimal to compare in pairs first?

Median can be done in linear time and is now down to (I think) $2.97n$. The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small. The following theorem, if true, may help improve ...
6
votes
0answers
249 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 ...
5
votes
0answers
1k 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....
5
votes
0answers
159 views

What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?

In the algebraic decision tree, the result is clear: Elmasry and Belal (Verification Of Minimum Redundancy Prefix Codes)'s lower bound shows that the worst case complexity of computing an optimal ...
4
votes
0answers
111 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\}...
4
votes
0answers
221 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
0answers
190 views

Type-and-effect systems, stochasticism and effect squelching: how about quicksort?

There's a feature of Haskell's type system which bugs me: you can't implement a randomized sorting algorithm without the use of randomness spilling out into all of its callers. That seems undesirable....
3
votes
0answers
51 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. ...
3
votes
0answers
184 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 ...
2
votes
0answers
96 views

Can you partially sort using $O(\log n)$ comparisons per element?

Input is a list of $n$ integers in an array A. Desired output is stored in Array B, such that $|rank(B[i])- i | \leq \sqrt{n}$. Can this be done using $O(\log n)$ comparisons per element? Just looking ...
2
votes
0answers
66 views

Cost of in-place partitioning integer arrays

Suppose we are given an array $a\colon[n]\to[m]$ of length $n$ (and each entry is between 1 and m). We will denote the $i$th entry of the array as $a[i]$. Task: Permute the array $a$ in-place so that ...
2
votes
0answers
163 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 ...
2
votes
0answers
68 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 ...
1
vote
0answers
465 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 ...
0
votes
0answers
85 views

Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
0
votes
0answers
42 views

2D-Interval partition problem

The classical interval partition Problem ascs for a minimal colouring of an interval graph: Let [a_i, b_i] be a collection of (closed) intervals (for i in {1,2,...,n} ). Find a partition of {1,2,...,n}...
0
votes
0answers
285 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): ...
0
votes
0answers
112 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 ...