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

learn more… | top users | synonyms

-2
votes
0answers
139 views

How to reduce the computational complexity max algorithm in this specific case

We work over $\mathbb{R}_+^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that ...
-1
votes
0answers
32 views

Reducing computational complexity of sorting algorithm in this specific case [duplicate]

We work over $\mathbb{R}^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}^L$) a vector that ...
2
votes
0answers
54 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
88 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
54 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
68 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
286 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
64 views

locality-aware Mergesort

Let $A$ be an array with a total order to be sorted. We say $A$ has locality $d$ iff each element is at most $d$ indices away from its final index in the sorted array. In the locality-aware mergesort, ...
0
votes
0answers
75 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
74 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
68 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
328 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 ...
2
votes
0answers
70 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
159 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
402 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
133 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
160 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
760 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
123 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
52 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
84 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
85 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
286 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
354 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
170 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
472 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
150 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
311 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
3k 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
257 views

Finding max of two elements in linear time with restriction

I have a matrix in the following form: ...
9
votes
1answer
242 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
182 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 ...
18
votes
3answers
729 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
456 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
158 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
364 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
583 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
276 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
350 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
441 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
403 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
211 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
483 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
218 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
221 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) ...