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
4 votes
0 answers
57 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
orlp's user avatar
  • 885
7 votes
1 answer
321 views

Is sorting NP-complete?

SORTING problem. Input: A poset which corresponds to a partially sorted list of different numbers. Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array. ...
domotorp's user avatar
  • 14k
2 votes
0 answers
150 views

What is best lower bound for comparison sort?

Sorting $n$ numbers requires $\lceil \log_2(n!)\rceil$ comparisons and this is asymptotically optimal, but there is an $O(n)$ error term. What is the best known lower bound for large $n$? I couldn't ...
domotorp's user avatar
  • 14k
1 vote
1 answer
66 views

Can arbitrary comparator be transformed into equivalent key for radix sort?

The question is quite simple: Is it possible for any deterministic comparator of keys to be transformed into radix-sortable key mapping function? By that I mean, does for every comparator ...
Kryštof Vosyka's user avatar
1 vote
1 answer
131 views

Algorithm for comparing list elements backwards

Input: A list of real numbers $[x_0, ..., x_n]$ Output: A list of integers $[d_0, ... , d_n]$ where $d_i$ is the largest $d\in\{1,\dots,i\}$ such that $$ x_i\geq x_{i-1}, x_{i-2},\dots,x_{i-d} $$ In ...
loop_orange's user avatar
6 votes
1 answer
578 views

Find odd-ranked numbers from a list

From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need? I could sort the whole list using $O(n\log ...
TZM's user avatar
  • 133
5 votes
2 answers
184 views

Lower bound for sorting without using a decision tree model

Can we prove the lower bound for the sorting problem just by Turing machine model? It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can ...
Hao Huang's user avatar
2 votes
1 answer
63 views

Sampling strategies for Quicksort

I'm studying a variation of Quicksort in which the algorithm samples a subarray of size $f(n)< n$ ($n$ is the size of the input array) and then chooses the pivot from this subarray. The pivot is ...
joeren1020's user avatar
6 votes
1 answer
495 views

Number of permutations that satisfy a given set of comparisons

We are given a set of comparisons of the form z[i] < z[j] for various i and j and an ...
Arthur B's user avatar
  • 429
13 votes
3 answers
2k views

Expected number of random comparisons needed to sort a list

Consider the task of sorting a list x of size n by repeatedly querying an oracle. The oracle draws, without replacement, a random pair of indices (i, j), with i != j, and returns (i, j) if x[i] < x[...
Arthur B's user avatar
  • 429
3 votes
0 answers
115 views

Linear time in-place stable sort

Surprisingly, linear time in-place stable sort is possible with integer keys of $O(\log n)$ bit length. An algorithm appeared in Radix Sorting With No Extra Space (Franceschini, Muthukrishnan, ...
Dmytro Taranovsky's user avatar
0 votes
1 answer
54 views

Selecting unique records from a large dataframe with many duplicate records

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
Timeguy322's user avatar
3 votes
1 answer
77 views

Sorting multiple columns of a matrix

Let $A \in \mathbb{R}^{n \times k}$ be a matrix where each column contains all of the numbers from $\{1,\dots,n\}$ in some arbitrary order. For example, if $n=3, k=2$, we could have $$ A = \begin{...
Claudio Moneo's user avatar
0 votes
0 answers
78 views

Low-Treewidth Sorting Networks

It was previously asked if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}_n$ on $n$ inputs. While a construction using online algorithms and the ...
Cornelius Brand's user avatar
0 votes
2 answers
370 views

Finding top-K items in a sliding window

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
Roman's user avatar
  • 233
0 votes
1 answer
122 views

What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?

In particular, the genesis of this idea was the notion that you could minimize the number of passes through the list in a comb sort by using the primes as a way to guarantee that every element gets ...
Tor Diryc'Goyust's user avatar
0 votes
1 answer
156 views

A sorting algorithm that uses the minimum comparasions possible

I'm looking for a sorting algorithm that minimizes comparisons instead of time complexity. The algorithm shouldn't compare any two elements for which the relation between them can be derived from ...
D. Pardal's user avatar
  • 103
6 votes
0 answers
165 views

Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$

This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$. The computation model we are considering is the unit-cost RAM machine with linear ...
Louis's user avatar
  • 775
3 votes
0 answers
151 views

Minimum feedback arc set for dense directed graph

This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
Ben Southworth's user avatar
5 votes
0 answers
164 views

Height of AVL tree with random elements

I know that for an AVL tree of N nodes, the depth of the tree is bounded by $$ \log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$ where $c,b$ are taken from the golden ratio linked to the worst ...
Binou's user avatar
  • 171
6 votes
1 answer
475 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 ...
GM1's user avatar
  • 169
2 votes
0 answers
105 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 ...
Vk1's user avatar
  • 137
2 votes
0 answers
99 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 ...
boinkboink's user avatar
6 votes
1 answer
286 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 ...
user avatar
-2 votes
1 answer
174 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 ...
multiplex's user avatar
2 votes
2 answers
243 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 ...
Turbo's user avatar
  • 12.9k
-1 votes
1 answer
70 views

Formally prove that the loops of this sorting algorithm will terminate [closed]

Given is the sorting algorithm Bubblesort ...
kathelk's user avatar
  • 117
3 votes
1 answer
198 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 ...
2016310588's user avatar
4 votes
0 answers
163 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\}...
zeb's user avatar
  • 376
15 votes
1 answer
605 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 (...
Dmytro Taranovsky's user avatar
3 votes
0 answers
97 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. ...
Dmytro Taranovsky's user avatar
6 votes
3 answers
474 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 ...
Joshua Herman's user avatar
7 votes
1 answer
483 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 ...
Chirag Jain's user avatar
-5 votes
1 answer
496 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 ...
Zazaeil's user avatar
  • 212
12 votes
1 answer
1k 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 ...
kodlu's user avatar
  • 2,070
4 votes
0 answers
305 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 ...
Artimis Fowl's user avatar
3 votes
1 answer
131 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?
Vk1's user avatar
  • 137
18 votes
2 answers
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 ...
a3nm's user avatar
  • 9,269
8 votes
1 answer
310 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 ...
J..y B..y's user avatar
  • 2,776
12 votes
2 answers
1k 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 ...
a3nm's user avatar
  • 9,269
6 votes
2 answers
189 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 ...
Thatchaphol's user avatar
  • 1,130
4 votes
1 answer
461 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 ...
Elliot Gorokhovsky's user avatar
2 votes
0 answers
210 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 ...
shaunc's user avatar
  • 211
9 votes
1 answer
516 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 ...
Vincent's user avatar
  • 307
0 votes
2 answers
239 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 ...
user40545's user avatar
  • 143
11 votes
2 answers
288 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 ...
a3nm's user avatar
  • 9,269
7 votes
1 answer
241 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 ...
user avatar
2 votes
0 answers
110 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 ...
Dolan Antenucci's user avatar
5 votes
1 answer
299 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?
Peter's user avatar
  • 53
16 votes
1 answer
273 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 ...
domotorp's user avatar
  • 14k