Lesson#6, Python 3

Lesson#6

# Insertion Sort
        # Example List: [54, 26, 93, 17, 77, 31]
    
                #            sorted     unsorted part
                # Example: [   54   | {26}, 93, 17, 77, 31 ]
                #            sorted     unsorted
                # -------> [ 26, 54 |  {93}, 17, 77, 31 ]
            # -------> [ 26, 54, 93 |  {17}, 77, 31 ]
        # -------> [ 17, 26, 54, 93 |  {77}, 31 ]
    # -------> [ 17, 26, 54, 77, 93 |  {31} ]
# -------> [ 17, 26, 31, 54, 77, 93 | ]

# Idea: Split the list into 2 parts - sorted and unsorted part
# Take the first element in "unsorted part" and
# Analyze its location in the "sorted part"

def InsertionSort(alist):
    length = len(alist)
    for position in range(1, length): # 1, 2, 3
        currentValue = alist[position] # = {17}
        while position > 0 and alist[position-1] > currentValue:
            alist[position] = alist[position-1]
            position = position - 1 # 3->2
        alist[position] = currentValue 
        print ('Updating: ', alist)

return alist

alist = [54, 26, 93, 17, 77, 31]
print (InsertionSort(alist))


run \| edit \| history \| help	0