Skip to main content
2 votes

Sorting Algorithm that accounts for relative difference to reduce comparisons (sorting paint samples)

If you have the exact $a/b$ when comparing two elements $a$ and $b$, you can easily sort in $n-1$ comparisions by finding all the $k_i$ values where $k_i \cdot a_0 = a_i$ and sorting that by any ...
EnEm's user avatar
  • 664
1 vote

A decision tree proof for the lower bounds worst case of an algorithm that k-nearly sorts an Array

I'll assume that the arrays do not have any repeated numbers, so we can treat the input and output arrays as a permutation of $1,2,\dots,n$. For each output permutation, there are at most $(2k+1)^n$ ...
D.W.'s user avatar
  • 162k
1 vote

Sorting Algorithm that accounts for relative difference to reduce comparisons (sorting paint samples)

I'll assume you believe that the right model is that you observe a "truncated normal distribution" centered at $\log(a/b)$. Then a reasonable approach might be to combine maximum likelihood ...
D.W.'s user avatar
  • 162k
1 vote

Minimal k-way comparison sorting algorithm?

If you need to give the comparisons beforehand, you unfortunately need n^2/2 comparisons, because if items x and y are consecutive after sorting, you must have compared them. On the other hand you ...
gnasher729's user avatar
1 vote

Algorithm to sort array into K increasing subsets?

First, consider the case when $k$ is a perfect power of $2$. You find the median of the input array in $O(n)$ time using the Selection algorithm. Now take the median as the pivot to partition the ...
codeR's user avatar
  • 1,742

Only top scored, non community-wiki answers of a minimum length are eligible