1
$\begingroup$

I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order from best to worst, in what way should the judge taste the chili from the individual bowls to complete the task of ranking with as small a number of repeat tastings of the same bowl as possible? The initial approach I thought of was as follows. I've named the bowls A - J:

initial order:

A, B, C, D, E, F, G, H, I, and J

Taste A then taste B. If B is better than A, switch them around in the order.

Judge thinks B is better than A:

B, A, C, D, E, F, G, H, I, and J

Taste A then taste C. If C is better than A, switch them around in the order.

Judge thinks C is better than A:

B, C, A, D, E, F, G, H, I, and J

Already though there is a problem. What if C was also better than B? We could complete the process then repeat again but its not clear to me how many times the process would have to be repeated in order to have everything ranked properly. What kinds of algorithms are these? Where can I learn more about them. Thanks.

$\endgroup$
1

2 Answers 2

1
$\begingroup$

If the tastings are reliable (i.e. always returning the same results for the same samples and forming a true total order relation - A better than B and B better than C implies A better than C), what you are after is a "minimum comparison sorting" procedure.

The number of comparisons for N elements is very close to N.Log2(N), but the exact procedure depends on N in a non trivial way, and not all configurations require exactly the same numer. https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list


As far as I know, there has been no study on minimizing the number of comparisons involving the same element (which could be understood as minimizing the largest number of comparisons with the same element).


Also note that an efficient sorting procedure cannot be static, i.e. work with a predefined set of comparisons. On the opposite, the outcome of the first tests decide which next tests should be performed. A purely static procedure should be exhaustive, i.e. require N(N-1)/2 comparisons.

$\endgroup$
0
$\begingroup$

Analytic hierarchy process (AHP) is a way to maximize or minimize or rank or prioritize things which are given in data formulated as qualitative comparisons, like a customer likes A more than B and so on. Given a set of customers and all their preferences, AHP can provide the max or a 'best' ranking or something like this.

See: https://en.wikipedia.org/wiki/Analytic_hierarchy_process

$\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.