Unanswered Questions
182 questions with no upvoted or accepted answers
10
votes
0
answers
1k
views
Complexity of Sorting Integers on a Multitape Turing Machine
How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
- 5,962
7
votes
0
answers
557
views
What is the average-case running time of Fun-sort?
I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
- 1,090
6
votes
0
answers
1k
views
How to sort a queue using a temporary stack?
Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack
We are allowed to make only two actions:
Action "x": Dequeue an element from the queue and push it ...
6
votes
0
answers
56
views
Level sums, displacements: how to determine their effect efficiently?
Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$,
$\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.
Define $$S(\delta,m) = ...
- 241
6
votes
0
answers
1k
views
Time complexity of obtaining the support set of an unsorted sequence?
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
- 1,025
6
votes
0
answers
292
views
Is greedy minimax permutation rejecting sorting optimal?
I sketch an impractical, theoretical comparison sort.
Initialize a list of all $n!$ permutations of size $n$.
For each possible pair of indices $i, j$, count how many permutations would get rejected ...
- 73.1k
5
votes
0
answers
134
views
Partitioning through block moves to the end
Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements ...
- 7,603
5
votes
0
answers
771
views
Sorting in place & stable in linear time
Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics-
The algorithm runs in $O(n)$ time.
The algorithm is stable.
The algorithm sorts in ...
- 280
5
votes
0
answers
98
views
What are applications to sort plain integer arrays?
A lot of research and engineering effort is put into finding fast methods
to sort an array of integers; e.g., Java's runtime library has highly-tuned
methods to sort arrays of each primitive type (see ...
- 4,536
5
votes
0
answers
517
views
Is there any recent study about percentage that computer spend on sorting?
I came across this on Art of Computer Programming long time ago
Computer manufacturers of the 1960s estimated that more than 25 percent
of the running time on their computers was spent on sorting,...
- 73.1k
5
votes
1
answer
8k
views
Merge two sorted arrays without using additional memory
We have two sorted arrays of integers.
Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
4
votes
0
answers
73
views
Deterministic solution of "nuts and bolts" problem
How are the samples in "Matching nuts and bolts" paper in chapter two chosen deterministically to achieve $O(n^{1.5})$ complexity? I don't see how projective planes can help here.
- 41
4
votes
0
answers
140
views
Comparison-based computation: percentage of current software development?
Vol. III of The Art of Computer Programming, chapter 5 (Sorting, intro) mentions:
Computer manufacturers of the 1960s estimated that more than 25
percent of the running time on their computers was ...
4
votes
0
answers
139
views
A container sort (or "Minecraft sort")
Here's the problem: I have some $n$ ordered containers, each with $m$ slots. I have $p$ temporary slots that I can use to move items between containers. Sorting within containers is not costly, ...
- 141
4
votes
0
answers
169
views
Perfect Halver Construction?
A sorting network is a circuit-based approach to sorting, built out of CompareExchange gates, which compute the function:
$$\mathsf{CompareExchange}(x,y) = (\min(x,y), \max(x,y))$$
The input to the ...
- 288