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

learn more… | top users | synonyms

0
votes
0answers
57 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): ...
-2
votes
1answer
55 views

Practical topological sorting for dependency graphs [closed]

I have been reading the Wikipedia page on Topological Sorting, specifically the depth-first algorithm which also detects cycles while it is building the sort. But from some experimentation with this ...
4
votes
1answer
59 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
322 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 ...
1
vote
0answers
50 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
152 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 := ...
0
votes
0answers
20 views

What's the official name for time-driven parallel informed sorting methods?

If you have a set $\Delta = \{A,B,C,D,E,...\}$ and you want to sort $\Delta$ based on a certain quality of the elements $\in \Delta$, then you can use a certain classification or ranking algorithm $R$ ...
11
votes
2answers
399 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
119 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
153 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)$ ...
13
votes
2answers
615 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 ...
11
votes
0answers
119 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
51 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
81 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$ ...
1
vote
1answer
79 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
283 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 ...
11
votes
2answers
351 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]} ...
2
votes
1answer
163 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?
11
votes
3answers
461 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
144 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 ...
3
votes
0answers
278 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 ...
9
votes
3answers
2k 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 ...
3
votes
2answers
137 views

Sort with random deviations

I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a ...
2
votes
1answer
254 views

Finding max of two elements in linear time with restriction

I have a matrix in the following form: ...
9
votes
1answer
237 views

Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?

Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness. One can see that inserting elements of an array into a binary search tree and reading them back ...
3
votes
1answer
180 views

A weighted sorting problem

Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized. It can be formulated as ...
17
votes
3answers
713 views

Sorting using a black box

Assume that we want to sort a list $S$ of $n$ real numbers. Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly. How much advantage can we gain using this black box? ...
3
votes
2answers
430 views

Finite state transducer that sorts

Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers ...
4
votes
0answers
156 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 ...
8
votes
1answer
350 views

Can we get a sorted list from a sorted matrix in $O(n^2)$

I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$. I proceed by assuming that it can be done ...
0
votes
1answer
556 views

Near-Sort quicksort algorithm faster than O(nlgn) [closed]

Here, we define a nearly-sorted array with k-sized error, as this: Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices. For example: 1, 2, 3, 6, ...
8
votes
1answer
271 views

Complexity of sorting

It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$. If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the ...
2
votes
1answer
344 views

Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time

Does there exist a stable comparison sort using $O(1)$ auxiliary memory and achieving $O(n \log n)$ average run time? Context: There are comparison sorts with any two of those three desirable ...
7
votes
1answer
416 views

Efficiently finding the minimum number of transpositions needed to sort a list

I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are. For example, the list [1, 1, 2, 0] ...
21
votes
1answer
397 views

Approximate 1d TSP with linear comparisons?

The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way ...
-2
votes
1answer
202 views

Sorting : proof for lower bound of Sorting [closed]

I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have ...
23
votes
2answers
1k views

Exact number of comparisons to compute the median

Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element ...
-5
votes
2answers
445 views

Proof of correctness of in-place Quick sort

I have found proof of correctness of Quick sort (not in-place version), Please refer me a proof of correctness of in-place Quick sort, or provide proof here is very appropriated. a typical ...
9
votes
2answers
209 views

Asymptotic complexity of sorting using k-comparisons

Sorting using 2-elements comparisons has an asymptotic worst-case complexity of $n \log_2(n)$ (reached by mergesort, heapsort, binary insertion, ford-johnson at least), which is optimal. If we sort ...
6
votes
2answers
220 views

Are there [good/optimal] parallel comparison sorts?

Comparing each pair of elements and sorting according to [[number less than] minus [number greater than]] is a parallel comparison sorting algorithm with a depth of $1$ comparison and ...
-10
votes
2answers
1k views

Are sorting algorithms approaching linear time? [closed]

I see some algorithms can do sorting in O(nloglogn) time. Is it reasonable to assume that as research progresses, more and more will be done to logarithm the extra time e.g. next research will produce ...
1
vote
0answers
115 views

How much variation is allowed before an algorithm is no longer a quicksort? [duplicate]

Possible Duplicate: When are two algorithms said to be “similar”? Generic Overview of promblem: I read somewhere once that a quicksort could be done without recursion in O(1) ...
5
votes
0answers
147 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 ...
7
votes
1answer
275 views

Optimal comparison-based stable sorting in constant space

For a comparison based sorting algorithm, it is desirable to: Be stable Run in $O(n\ \log n)$ Operate in $O(1)$ space I can find algorithms that satisfy any two of these but I can't find any that ...
9
votes
2answers
206 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], ...
16
votes
2answers
870 views

Sorting by Euclidean distance

$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$. A no-brain approach is to ...
10
votes
2answers
603 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 ...
5
votes
1answer
644 views

what advantage does heapsort has over smoothsort?

Wikipedia states that the advantages of smoothsort over heapsort is that at times it comes closer to O(n) time. Now I was wondering what advantage does heapsort has over smoothsort? Or to rephrase ...
18
votes
1answer
579 views

Merging lists of fragile objects

Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log ...
3
votes
1answer
301 views

Parallel sorting: introduction and state of research

there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic. So, do you know a good summary or introduction into parallel sorting algorithms? In ...