**Insertion sort algorithm -**In the last couple of articles, we studied Bubble sort and Selection sort algorithms. In this article, we will learn about another sorting algorithm - Insertion sort. Just like Bubble sort and selection sort, time complexity of this algorithm is O(n^2) and space complexity being O(1).

#### Selection Sort Algorithm

1. First element i.e. element at index 0 is always sorted and is the part of sorted sub-list 2. Select next element 3. Compare it with all elements in sorted sub-list 4. If the value of the element is smaller, swap it with the element(s) in sorted sub-list 5. Continue till we get an element from sorted sub-list which is smaller than the element 6. Insert the element in the sorted sub-list 7. Get the next element 7. Repeat this process for selected element

#### Example

Consider the following list-

Initially, the first element in the list is already sorted. Hence we add that to sorted sub-list identified with green color.

**Iteration 1:**

Compare element at index 1 with the elements in sorted sub-list and insert at appropriate location. Here,

`array[0] > array[1]`

, so `array[1]`

should appear before `array[0]`

. Hence we swap them to adjust their positions.**Iteration 2:**

In this case,

`array[2] > array[1]`

, hence nothing needs to be required as it is already at appropriate position.**Iteration 3:**

In this case,

`array[3] < array[2]`

, so we swap them so that `array[3]=7`

and `array[2]=1`

. Now, `array[2]`

which is `1`

is again less than `array[1]`

, so we swap them again such that `array[1]=1`

and `array[2]=5`

. Now also, `array[1] > array[0]`

, so we swap these elements such that `array[0]=1`

and `array[1]=3`

and we are done.**Iteration 4:**

**Iteration 5:**

**Iteration 6:**

**Iteration 7:**

#### Python Implementation:

def insertion_sort(array): n = len(array) for i in range(1, n): j = i current = array[j] while j > 0 and array[j-1] > current: array[j] = array[j-1] j -= 1 array[j] = current my_array = [5, 3, 7, 1,4, 8, 2, 6] insertion_sort(my_array) print my_array

**Output:**

[1, 2, 3, 4, 5, 6, 7, 8]

## 0 comments:

## Post a Comment