#Jonathan Hudson
#Student Number 12347890
#Date: 2020-08-26
#Lecture Practice

# Jonathan Hudson
# Sort a list of values using insertion sort

def swap(values, i, j):
  temp = values[i]
  values[i] = values[j]
  values[j] = temp

def swap2(values, i, j):
  values[i], values[j] = values[j], values[i]

# Perform insertion sort on list of numerical values (smallest to largest)
# Parameters
#             values: a list of numerical values to insertion sort
# Returns
#             nothing is returned
#             values contains same items but is ordered in increasing numerical value
def insertionSort(values):
  # A list consisting of only value at index = 0 is a sorted list of length 1
  # We will start at index 1 and loop to end of list
  #    we will move the item at each index into a sorted position
  i = 1
  while i < len(values):    
    #Start while loop at newest item index
    j = i    
    #Loop down until item is at front of list or item is in sorted position
    while j > 0 and values[j-1] > values[j]:
      #Move item that is greater than value towards end of list
      swap(values, j, j-1)      
      #Change index to next item towards front of list
      j -= 1      
    #Move to the next unsorted index of list
    i += 1

    
# List of values
values = [1, 3, 7, 5, 9, 2, 6, 8, 4, 0]

print(values)
insertionSort(values)  
print(values)