Insertion Sort¶

• Ever played any card game? Well, that's what is insertion sort.

• Idea:

  • Consider the very first element of the array(element at the 0th index) to be sorted. That would also be the left array and hence the first for loop will start from index 1.
  • Now you are at index 1, compare this with the left sorted array until you find this element to be larger than any element in the left array(obviously taking care that you are within the array bound) and keep copying the larger elements.
  • Once done, copy this element to the place where it is larger than the last found element.

• Time Complexity:

  • Best case: $O(n)$
  • Worst Case: $O(n^{2})$

• Space Complexity: $O(1)$

In [6]:

def insertion(arr):

    for i in range(1, len(arr)):
        idx = i
        element = arr[idx]
        while element < arr[idx - 1] and idx > 0:
            arr[idx] = arr[idx - 1]
            idx -= 1
        arr[idx] = element

    return arr

def insertion(arr): for i in range(1, len(arr)): idx = i element = arr[idx] while element < arr[idx - 1] and idx > 0: arr[idx] = arr[idx - 1] idx -= 1 arr[idx] = element return arr

In [7]:

arr = [10, 1, 7, 4, 8, 2, 11]

arr = [10, 1, 7, 4, 8, 2, 11]

In [8]:

insertion(arr)

insertion(arr)

Out[8]:

[1, 2, 4, 7, 8, 10, 11]

In [ ]: