Question

Write a Program to implement Insertion sort

Answer 1

Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.

Sorting algorithm 

for i=1 to a.length 

key = a[i]

insert a[i] into sorted sequence a[1.........i-1]

j = i - 1

while j > 0  and a[j] > key 

a[j + 1] = a[j]

j = j - 1

a[j + 1] = key

For eg : [ 13, 12, 14, 5, 6 ]

Let 's loop for i = 1 to 4 

i = 1. as 12 is smaller than 13, move 13 and insert 12 before 13
[12, 13, 14, 5, 6 ]

i = 2. 14 will remain at the same location as all elements in A[0..I-1] are smaller than 14
[12, 13, 14, 5, 6]

i = 3. 5 will move at the beginning and other elements from 12 to 14 will move one position to front from their current location.
[5, 12, 13, 14, 6]

i = 4. 6 will move to the position after 5, and elements from 11 to 13 will move one position to front of their current position.

[5, 6, 12, 13, 14]

Program

# Python program for implementation of Insertion Sort 

  

# creating a Function to do insertion sort 

def insertion_Sort(arr): 

  # Outer Loop to 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 = j-1

      arr[j+1] = key

  return arr

  

# Driver code to test above 

arr = [80, 10, 60, 40, 70, 50] 

print("Unsorted array is:", arr)  

print ("Sorted array is:",insertion_Sort(arr))

---

Output :

Unsorted array is: [80, 10, 60, 40, 70, 50] 

Sorted array is: [10, 40, 50, 60, 70, 80]

---

Complexity in Insertion Sort

The Time complexity of the insertion sort is - O(n²). 

It uses the two loops for iteration.

In the worst case, each element is compared with all the other elements in the sorted array. For n elements, there will be n² comparisons. Therefore, the time complexity is O(n²)

The Auxiliary space in insertion sort: O(1)

All the variables are declared in the global frame.

Conclusion

Insertion sort is efficient for small lists or arrays. It is a little bit slow for large datasets.

Insertion sort is a simple and inefficient algorithm that has many advantages, but there are more efficient algorithms are available.

In this post, we have covered the concept of the insertion sort and its implementation with an example using the Python programming language.

---

For more Rajasthan Technical University CSE VI Sem Python Lab Experiments Click here