# 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 = 3:
input = ["B","C","A"]

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

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

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

# For printing of info (on the associated leaf in the relevant
# decision tree in a figure in the course material) at the end of the
# program:
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()

# For two of the example inputs given above, point out the
# correspondence of the output to figures in the course material:
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/F26/insertionsort4elm.pdf .
"""
)
if copyOfInput == ["B","C","A"]:
  print(
"""The information (i.e., the element indices) printed above appears
on the path from the root to leaf number 3 (counted from left to
right) in the decision tree for InsertionSort, n=3, in the book and
also included on page 3 of these slides:
https://www.imada.sdu.dk/u/rolf/Edu/DM507/F26/sortingInLinearTimeSlides_NoOverlays.pdf
.  """
)