# Tag Info

Accepted

• 18.2k

### Sorting a programs instructions until it works

Others have pointed out this is semidecidable. In most programming languages, the problem is NP-hard. In particular, the following problem is NP-hard: Input: a set of lines of code Question: does ...
• 12.3k

### Necessary and sufficient number of comparisons by every element to fully sort a set of n elements?

Note that in a sorting network, the number of times an element is compared is bounded by the depth of the network. There are several simple sorting networks of depth $O((\log n)^2)$. The AKS network ...
• 556
Accepted

### "Almost sorting" integers in linear time

As it turns out, my question is quite irrelevant after all. Indeed, I am working on the RAM machine with uniform cost measure (i.e., we have registers whose registers are not necessarily of constant ...
• 9,697

### Lower bound for sorting without using a decision tree model

If you are speaking specifically of sorting lists of integers on a multitape TM, then I think the answer is no. For example, comparison-based sorts, when implemented on a TM and sorting integers of ...
• 37.8k

### Is sorting NP-complete?

This is not a full answer, but some partial pieces of information (which you might already be aware of). This is related to the number of linear extensions of the poset. It is known that the worst-...
• 881

### finding smallest k elements in array in O(k)

First use $O(n)$ to build a min-heap. It is known that we can use $O(k)$ to find the $k$ smallest elements in a min-heap: Frederickson, Greg N., An optimal algorithm for selection in a min-heap, Inf....
• 112
Accepted

### Formally prove that the loops of this sorting algorithm will terminate

Since the loop variables $i$ and $j$ are not modified in the loop body, you can compute the exact number of iterations. The inner loop is executed $n-i$ times in each iteration of the outer loop, so ...
Accepted

### A sorting algorithm that uses the minimum comparasions possible

Using simple methods, it can be shown that any comparison-based algorithm must perform at least $n\log{n}-o(nlogn)$ comparisons. This bound is obtained (up to lower terms) by the binary insertion sort ...

### Lower bound for sorting without using a decision tree model

The paper "Sorting and Element Distinctness on One-Way Turing Machines" by Holger Petersen shows a lower bound for sorting on a Turing machine with one work tape and one-way input.
• 4,640
Accepted

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

does for every comparator C(key) exist a function M(key) such that sorting by C gives the same result as radix-sorting by the output of M? SHORT ANSWER Not for non discrete value domains, but yes for ...
• 2,786