"""
insertion_sort.py

@author: paolo
"""
import random


def insertion_sort(A):
    """See CLRS 2.1 - uncomment print statements to view progress
    after each iteration of the outer loop"""
    for j in range(1,len(A)):
        #print(A)
        key = A[j]
        i = j-1
        while i >= 0 and A[i] > key:
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key
    #print(A)


def make_random_instance(n):
    """Just a random permutation of the first n integers."""
    A=range(n)
    random.shuffle(A)
    return A


# run as follows (from a unix shell or command prompt under Windows):
# python -i insertion_sort.py
# and then try the following at the python prompt:
# >>> A = make_random_instance(10)
# >>> A
# [0, 7, 4, 6, 9, 8, 5, 2, 1, 3]
# >>> insertion_sort(A)
# >>> A
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]