solution_134.py

#!/usr/bin/python3
# ====================================================================
# Python program for implementation of Insertion Sort
# From: www.geeksforgeeks.org/insertion-sort/#
#       This code is contributed by Mohit Kumra
# --------------------------------------------------------------------
# Time Complexity of Insertion Sort
#
# a. The worst-case time complexity of the Insertion sort is O(N^2)
# b. The average case time complexity of the Insertion sort is O(N^2)
# c. The time complexity of the best case is O(N).
# ====================================================================

# --------------------------------------------------------------------
# insertion Sort Function
# --------------------------------------------------------------------

def insertionSort(arr):

    # Traverse through 1 to len(arr)

    for i in range(1, len(arr)):

        key = arr[i]

        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position

        j = i-1

        while j >= 0 and key < arr[j] :
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key


# --------------------------------------------------------------------
# ---- main - Driver code to test above
# --------------------------------------------------------------------

arr = [ 12, 11, 13, 5, 6 ]

insertionSort(arr)

for i in range(len(arr)):
    print (f'[{i:2}] {arr[i]}')