Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
5
votes
2answers
1k 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 / ...
4
votes
0answers
95 views

Is there any efficient Network stable sort (not bubble sort)?

Ok, I realize Bitonic sort is not stable and any attempt to make it stable is inefficient, or is there some efficient way? But is there some other network sort which is indeed stable beside bubble ...
3
votes
1answer
127 views

how to achieve a topological sort of an given sequence with minimum swaps

For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum ...
7
votes
1answer
326 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 ...
11
votes
1answer
757 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 ...
15
votes
3answers
952 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 ...
-2
votes
1answer
161 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
16 views

Why is it more efficient to merge larger runs higher in the tree than perform a balanced tree of merges in an unbalanced ping-pong merge?

While studying the research paper published by Microsoft in 2014, I stumbled upon Unbalanced Ping-Pong Merge. In section 3.2 of the paper, it discusses about merging two sorted runs at a time. It ...
2
votes
0answers
100 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 ...
1
vote
3answers
1k views

Sorting array of distances by proximity to each other

I was playing with geolocation on maps and stumbled on an interesting problem: I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes ...
2
votes
0answers
73 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 ...
6
votes
1answer
165 views

Is sorting pairwise distances as hard as sorting arbitrary points?

If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances? Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as ...
16
votes
2answers
2k 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 ...
2
votes
2answers
202 views

Under what models do we know linear time sorting?

The best we know for general case sorting is $O(n\log n)$ (which is also $\theta(n\log n)$ is decision tree model) and the problem of $O(n)$ sorting is open for turing machine models. Under what ...
12
votes
4answers
7k views

finding smallest k elements in array in O(k)

This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the ...
-1
votes
1answer
64 views
4
votes
0answers
119 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
367 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
66 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
458 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 ...
11
votes
2answers
266 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 ...
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 ...
-5
votes
1answer
281 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
851 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
243 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 ...
34
votes
3answers
1k views

Comparison-based data structure for finding items

Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$? ...
3
votes
1answer
119 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?
8
votes
1answer
223 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 ...
6
votes
2answers
170 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 ...
12
votes
3answers
325 views

Sorting “k-tonic” sequences

I hope somebody knows a ref to this, so I do not have to read the literature... Consider a sequence of numbers $x_1, \ldots, x_n$. Think about the sequence as $n-1$ intervals $[x_1, x_2], [x_2, x_3], ...
4
votes
1answer
407 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 ...
7
votes
1answer
205 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 ...
5
votes
1answer
358 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" ...
2
votes
0answers
175 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 ...
5
votes
5answers
2k views

Sorting algorithm with a complexity smaller than $n \log n$?

If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input. But if we want to encode input, we ...
6
votes
0answers
256 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 ...
16
votes
2answers
2k views

What persistent data structure for a set of partially ordered elements?

I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable. One problem with hashtables is that two equal ...
-1
votes
2answers
234 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 ...
2
votes
0answers
73 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 ...
0
votes
1answer
289 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 ...
5
votes
1answer
257 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?
6
votes
5answers
7k views

is “spaghetti sort” really O(n) (even as a thought experiment) ?

I`m referring to the notion described here: http://en.wikipedia.org/wiki/Spaghetti_sort In the analysis section the author admits that considering it to be O(n) requires the assumption that the act ...
16
votes
1answer
253 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
194 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 ...
4
votes
1answer
163 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 ...
14
votes
0answers
390 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 ...
5
votes
1answer
599 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)$ ...
3
votes
1answer
110 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 | \...
1
vote
0answers
469 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
444 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 ...