-2
$\begingroup$

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this necessity and only operate on the sign of the sum of two elements which we are comparing right now?

This surely does not work for the general case, but what if we have a set of numbers and its complements for example.

$\endgroup$
5
  • $\begingroup$ Since $x > y \iff x - y > 0$ it is clear that if you can get the sign of the sum of two elements and if you do have the additive inverse of every element then you can do it. Or is there something I missed from your question? $\endgroup$
    – sebastian
    Commented Jun 15, 2019 at 19:26
  • $\begingroup$ This seems like a nice homework exercise. I assume by "a set of numbers and its complements" you mean your set of numbers is closed under negation. So, find the minimum and the maximum numbers: a number is the maximum (minimum) iff its sum with every other number in the set is non-negative (non-positive). So, find the minimum and the maximum, remove those, then recurse. $\endgroup$
    – Neal Young
    Commented Jun 17, 2019 at 14:28
  • 1
    $\begingroup$ @araomis Perhaps you aren't given which pairs of numbers are additive inverses of each other, but I guess you can find the additive inverse of a given element x by finding the element y such that x+y is zero. Then your method works. $\endgroup$
    – Neal Young
    Commented Jun 17, 2019 at 14:30
  • $\begingroup$ Right. Your interpretation makes sense to me. $\endgroup$
    – sebastian
    Commented Jun 17, 2019 at 14:51
  • $\begingroup$ @NealYoung is right with his assumption. I actually found a way to not sort them explicitly and reduce the complexity to Theta(nlogn) instead of Theta(N^2). Thank y'all for your input nevertheless! $\endgroup$
    – multiplex
    Commented Jun 17, 2019 at 15:30

1 Answer 1

1
$\begingroup$

If one has an algorithm that can sort a list of objects, then one can compare any two objects by applying the algorithm recursively to the set of just those two objects and seeing if the output of the algorithm is different from the input. So it doesn't seem that there is any meaningful way one can sort without effectively having a pairwise comparison operation as a precondition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.