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.
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]
# Python program for implementation of Insertion Sort
# creating a Function to do insertion sort
# 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
# Driver code to test above
arr = [80, 10, 60, 40, 70, 50]
print("Unsorted array is:", arr)
print ("Sorted array is:",insertion_Sort(arr))
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.
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