0
$\begingroup$

I'm looking for a sorting algorithm that minimizes comparisons instead of time complexity.

The algorithm shouldn't compare any two elements for which the relation between them can be derived from comparisons previously made. For example, given three elements $A$, $B$, and $C$ such that $A<B<C$, the algorithm shouldn't attempt to compare $A$ to $C$ if it already compared $A$ to $B$ and $B$ to $C$. (Of course, if the algorithm compared $A$ to $B$ and then $A$ to $C$, it would then also need to compare $B$ to $C$. That's okay.)

Since sorting algorithms have been studied for decades, I'm guessing there already exists an algorithm for this.

My use case is allowing a user to sort things by preference by showing two of those things side-by-side.

$\endgroup$
1
  • 4
    $\begingroup$ Do you care about the exact minimum (from your use case, sounds like probably not, but it's good to check), or just something "good enough"? Exact minimum is a complicated story, and is only known for sorting lists up to length 24 or so. $\endgroup$ Feb 10 at 16:31
2
$\begingroup$

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 algorithm (see e.g. [1] for a good introduction on the topic). There are also many other algorithms which obtain this bound asymptotically up to a constant factor, e.g quicksort (in expectation) and heapsort.

That said, for practical purposes I suggest you use the sorting algorithm already implemented in your prefered programming language, as it is most likely been highly optimized, and would work faster than if you implement it yourself, unless you have a very specially structured input.

[1] https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.79

$\endgroup$
5
  • $\begingroup$ Since asking the user is an asynchronous operation, using the built-in sorting algorithm in JavaScript is not possible. Binary insertion sort sounds like a good idea. $\endgroup$
    – D. Pardal
    Feb 10 at 18:28
  • 1
    $\begingroup$ I'm not sure I follow, but if you wish to implement the sorting algorithm yourself, you might want to consider quicksort as (a) it is very fast in-practice (b) it is very easy to implement, and (c) it works very well with CPU caching (though I am not an expert in the subject of in-practice sorting algorithms) $\endgroup$ Feb 10 at 19:13
  • $\begingroup$ Thanks for your suggestion. I'm not actually worried about the speed of the algorithm. The user choice is by far the biggest bottleneck; that's why I'm trying to minimize the number of comparisons. $\endgroup$
    – D. Pardal
    Feb 10 at 22:36
  • $\begingroup$ If you want to use it for user choices, you might want to use an oblivious sorting algorithm, so that the set of comparisons presented to the user does not depend on answer to the queries. Otherwise you would have to generate the queries dynamically based on the previously given answer, which I imagine is quite awkward from an UI point of view. $\endgroup$ Feb 11 at 6:45
  • $\begingroup$ Though, frankly, the whole setup sounds quite weird. Instead of asking $n\log n$ binary questions, why don’t you simply ask the user “rank these $n$ items according to your preference”? Given them an interactive list where they can move the items around. This also avoids another problem (or rather, shifts it to the user), namely that users’ binary choices most likely will not form a linear order, but a nontransitive tournament, so if you ask for $A<B$ and $B<C$ and infer $A<C$, the user will complain that they actually prefer $C<A$. $\endgroup$ Feb 11 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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