0
$\begingroup$

I want to sort the list of parameters (p1, p2, p3, p4, ..., pn) according to their importance. All parameters have to be compared with each other at best once, but not less than once.

The person will be asked to select the winner of the comparison, so for every comparison, there is only 1 winner.

The workflow should be similar to this:

  1. Compare p1:p2, p1:p3, p1:p4, p2:p3, p2:p4, p3:p4, ... as seen in the table below. Compare that many times that we can make an order without a doubt.
  2. Sort the parameters from most to least winning.
|    | p1 | p2 | p3 | p4 |
| p1 | xx | xx | xx | xx |
| p2 | p1 | xx | xx | xx |
| p3 | p3 | p2 | xx | xx |
| p4 | p1 | p4 | p3 | xx |

Sorted example (not in correct order): p4, p2, p3, p1

The problem with the comparison above is that there is not enough data to sort them all, so we need to compare further.

I don't know how to write an algorithm that will be suitable for the human comparison of a list with around 10 parameters.

$\endgroup$
2
  • $\begingroup$ "at best once, but not less than once": what ?? $\endgroup$
    – user16034
    Nov 29, 2022 at 7:44
  • $\begingroup$ "there is not enough data to sort them all, so we need to compare further": what ?? $\endgroup$
    – user16034
    Nov 29, 2022 at 7:45

2 Answers 2

1
$\begingroup$

I will assume that the importance relation is transitive, and in fact, forms a partial order.

If the algorithm is not free to choose which comparisons are done, but that was chosen by someone else and the algorithm just sees the results of those comparisons, then build a directed graph (with an edge from p1:p2 if you compared p1,p2 and p2 was more important), then perform a topological sort of this graph. The last item in the sorted list will be a candidate for which item is most important. Note that it might not be possible to determine uniquely which item is most important. For instance, if you compare p1:p2 and p1:p3 and find that p1 is less important in both cases, then you won't know whether p2 or p3 are the most important, but the topological sort will show you one possible ordering that is consistent with all of the comparisons you've done so far.

If the algorithm is free to choose which pairs are compared, use any comparison-based sorting algorithm. See https://en.wikipedia.org/wiki/Comparison_sort.

$\endgroup$
1
  • $\begingroup$ The graph can be drawn regardless. If it is not a partial order, it will mean that relative importance loses its meaning and cannot be determined. $\endgroup$
    – whoisit
    Dec 29, 2022 at 8:18
0
$\begingroup$

As "all parameters have to be compared with each other at best once*, but not less than once", you must perform at least $\frac12 n(n-1)$ comparisons and you can do it in the systematic way, like in your example. There is no shortcut.

*If you perform the same comparisons several times, there are two possibilities:

  • all comparisons come to the same conclusion, then this was useless extra work;
  • the results differ, then you are stuck, you can't sort the parameters.
$\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.