Order by pair comparisons

Order by pair comparisons is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Assume we have a set of items that can be sorted into an order by the user.

The user is presented with pairs of items from the set in no order, the user states which item is less than, equal to, or greater than the other (with respect to their relative positions if fully ordered).

Write a function that given items that the user can order, asks the user to give the result of comparing two items at a time and uses the comparison results to eventually return the items in order.

Try and minimise the comparisons the user is asked for.

Show on this page, the function ordering the colours of the rainbow:

   violet red green indigo blue yellow orange

The correct ordering being:

   red orange yellow green blue indigo violet

(Note that the seven colours can form twenty-one different pairs).

Python

Uses binary search to insert successive items into a growing ordered list. Comparisons are asked for.

<lang python>def _insort_right(a, x, q):

   """
   Insert item x in list a, and keep it sorted assuming a is sorted.
   If x is already in a, insert it to the right of the rightmost x.
   """

   lo, hi = 0, len(a)
   while lo < hi:
       mid = (lo+hi)//2
       q += 1
       less = input(f"{q:2}: IS {x:>6} LESS-THAN {a[mid]:>6} ? y/n: ").strip().lower() == 'y'
       if less: hi = mid
       else: lo = mid+1
   a.insert(lo, x)
   return q

def order(items):

   ordered, q = [], 0
   for item in items:
       q = _insort_right(ordered, item, q)
   return ordered, q

if __name__ == '__main__':

   items = 'violet red green indigo blue yellow orange'.split()
   ans, questions = order(items)
   print('\n' + ' '.join(ans))</lang>

Output:

 1: IS    red LESS-THAN violet ? y/n: y

 2: IS  green LESS-THAN violet ? y/n: y

 3: IS  green LESS-THAN    red ? y/n: n

 4: IS indigo LESS-THAN  green ? y/n: n

 5: IS indigo LESS-THAN violet ? y/n: y

 6: IS   blue LESS-THAN indigo ? y/n: y

 7: IS   blue LESS-THAN  green ? y/n: n

 8: IS yellow LESS-THAN   blue ? y/n: y

 9: IS yellow LESS-THAN  green ? y/n: y

10: IS yellow LESS-THAN    red ? y/n: n

11: IS orange LESS-THAN   blue ? y/n: y

12: IS orange LESS-THAN yellow ? y/n: y

13: IS orange LESS-THAN    red ? y/n: n

red orange yellow green blue indigo violet