# A Python script which illustrates how a comparison-based sorting
# algorithm (here Insertionsort) can be adapted to show the original
# index of the elements 1) each time two elements are compared and 2)
# in the final, sorted output. A run of the algorithm gives the
# numbers appearing in one path of the decision tree of the algorithm
# (and all such paths can be produced if the algorithm is run on all
# possible permutations of the input).

# Start by just running the script, to more easily understand how it
# functions. Maybe try all three suggested examples for input
# (uncommenting each in turn).

# Decorate elements with their start indices (1-indexed indices):
def annotateInput(l):
    return list(zip(l,range(1,len(l)+1)))

# INSERTIONSORT:
def InsertionSort(input):
    for i in range(1,len(input)):
        j = i
        while j >= 1 and less(input[j], input[j-1]):
            input[j-1], input[j] = input[j], input[j-1]
            j -= 1

# A comparison function, which also prints the indices of the elements
# compared.
def less(elmX,elmY):
    print(f"Is x{elmY[1]} > x{elmX[1]}? ", end="")
    if elmX[0] < elmY[0]:
        print ("Yes")
        return True
    else:
        print ("No")
        return False
    

# One potential input of length n = 4:
input = ["C","A","D","B"]

# Another input with the same (un)order:
#input = ["53","51","54","52"]

# Another input with a different (un)order:
#input = ["D","B","C","A"]

# For printing of info (on the associated leaf in the relevant
# decision tree) at the end:
copyOfInput = input[:]

annotatedInput = annotateInput(input)

print(f"The input {input} annotated with indices becomes:")
print()

print(annotatedInput)
print()
print("which we refer to as:")
print()
print([f"x{i+1}" for i in range(len(input))])
print()

print("Running InsertionSort on input gives the following comparisons:")
print()
InsertionSort(annotatedInput)

print()
print("After sorting, the output is:")
print()
print(annotatedInput)
print()
print("Which can also be stated as:")
print()
print([f"x{elm[1]}" for elm in annotatedInput])
print()
if copyOfInput == ["C","A","D","B"]:
  print(
"""The information (i.e., the element indices) printed above appears
on the path from the root to leaf number 15 (counted from left to
right) in the following decision tree for InsertionSort, n=4:
https://www.imada.sdu.dk/u/rolf/Edu/DM507/F25/insertionsort4elm.pdf .
"""
)