# Write a Program to implement Insertion sort

1 like 0 dislike
627 views
Write a Program to implement Insertion sort
 Where can I do online courses From Word's Top Instructors? UDEMY:: Attend All Udemy Courses in Just INR 450[Coupon] Coursera:: Join For FREE

1 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

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(1len(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 = [801060407050

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(n2).

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 n2 comparisons. Therefore, the time complexity is O(n2)

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.