Python preference finder - how to implement binary insertion sort

Question

I am creating a program which takes a file with a new 'thing' on each line. For testing, I am using NBA basketball teams (which there are 30 of). It asks the person A vs. B, until it can create a full list of their favourite to least favourite 'thing'.

So far, this works a charm, but asks too many questions. I have read and understood an answer regarding binary insertion sort, found here: https://stackoverflow.com/a/33748286/8419835 However, I am having trouble implementing it with how I currently have my code structured.

options = []
toPrint = []
with open("list.txt", "r") as f:
    for line in f.read().splitlines():
        options.append(dict(name=line,superiors=[],inferiors=[],active=False))

print()
for o in options:
    o['active'] = True
    for c in options:
        if c != o and c['active'] and o['name'] not in c['superiors'] and o['name'] not in c['inferiors'] and c['name'] not in o['superiors'] and c['name'] not in o['inferiors']:
            choice = input(o['name'] + ' (1) or ' + c['name'] + ' (2) ? : ')
            if choice == '2':
                c['inferiors'].append(o['name'])
                c['inferiors'].extend(o['inferiors'])
                o['superiors'].append(c['name'])
                o['superiors'].extend(c['superiors'])
                c['inferiors'] = list(set(c['inferiors']))
                o['superiors'] = list(set(o['superiors']))
            else:
                o['inferiors'].append(c['name'])
                o['inferiors'].extend(c['inferiors'])
                c['superiors'].append(o['name'])
                c['superiors'].extend(o['superiors'])
                o['inferiors'] = list(set(o['inferiors']))
                c['superiors'] = list(set(c['superiors']))

print()
for x in range(30):
    for o in options:
        if len(o['superiors']) == x:
            toPrint.append(o['name'])
for x in range(30):
    print(str(x + 1) + '. ' + toPrint[x])
print()

Does anyone have any ideas on how I can take the code I currently have, and modify it so that it asks the minimum possible amount of questions, as seen in the link above?

Answer 1

Consider an example: we will make a rank among {A,B,C,D,E,F}
We can take a container which will hold the final order serially.
Initially container =[] Now we will iterate through our given list :

1. First iteration for A,container=[], as container is empty we can easily store A. After iteration container =[A]

2. Second iteration for B,container=[A], we can insert B by asking only one question. After iteration container =[A,B] or [B,A]

3. During third iteration, we can ask two questions to find c's position and insert C

4. During fourth iteration, we can ask 3 questions and insert D

5. During fifth iteration, we can ask 4 questions and insert E

6. During nth iteration, we can ask n-1 questions and insert nth element in its

So we will need O(n*(n-1)) times query or asking to rank among them.
But we can decrease this number to O(n*(logn)) by using binary search.
Each time when we searching for an elements position we can use binary search for finding its position because if A > B and B >C then A > C.

Code:

options = []
toPrint = []
with open("list.txt", "r") as f:
    for line in f.read().splitlines():
        options.append(line)

print()

curren_list=[]
cnt=0
for o in range(0,len(options)):
    lo=0
    hi=len(curren_list)-1
    index=0

    while lo<=hi:
        mid=int((lo+hi)/2)
        choice = input(curren_list[mid] + ' (1) or ' + options[o] + ' (2) ? : ')
        cnt=cnt+1
        if choice=='1':
            lo=mid+1
            index=mid+1
        else:
            hi=mid-1

    curren_list=curren_list[0:index]+[options[o]]+curren_list[index:len(curren_list)]

print("Number of asking: ",cnt)
print()
for x in range(len(curren_list)):
    print(str(x + 1) + '. ' + curren_list[x])
print()