Insertion Sort using Python

Insertion sort is a type of sorting technique that is used for sorting an array with random elements. Using sorting methods, any unsorted array can be sorted into ascending or descending order. Insertion sort is one way to do it. In this sorting technique, the array is divided into two parts. One is the sorted array, and the other is the unsorted array. We pick one element from the unsorted part of the array and place that element in its correct position in the sorted part of the array.

The implementation of insertion sort is quite easy and simple. It is an in-place sorting technique which means it does not need any extra space for sorting the elements. It sorts the elements in the same memory space in which the input elements are sorted. It is also a stable sorting technique meaning that the elements get sorted in the order in which they are entered in the array. For example, if we have the same multiple elements in the array, the element that comes first in the unsorted array will also come first in the sorted array.

• The array elements are traversed from the first to the last index. In other words, we can say that the array is traversed from 1 to n.
• If the array element at position i is greater than its predecessor, which is the element at (i-1)th index, it does not need to be moved.
• If the array element at position i is less than its predecessor, which is the element at (i-1)th index, it needs to be moved or shifted towards the left until we find a predecessor which is smaller than it or if we reach the first element or the leftmost position in the array.

Code for insertion sort using python

def insertion_sort(arr):
 
    # Traverse the array from the first to the last element
    for i in range(1, len(arr)):
 
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
 
list1 = [11,7,43,22,3,19]
insertion_sort(list1)   
list2 = [] 
print("Sorted array is : ")
for i in range(1, len(list1)):
  list2.append(list1[i])       
print(list2)

Output

Sorted array is : 
[7, 11, 19, 22, 43]

Explanation

In the above code set, we have created a function called insertion_sort(arr). Inside the function, we defined for loop for traversing the array from the first element to the last element or traversing the element from 1 to len(arr). In for loop, assigned a value of arr is key. Every time the loop iterates, the new value will assign to the variable value key. Now, we have used another variable, and we have used the while to check whether the j is greater or equal to 0 and the value is smaller than the first element of the list. If both conditions are true, then we will move the first element to the 0^th index and reduce the value of j by one index, and so on. In the end, we will copy the value of the list1 to another list named list2 and print the result.

Time Complexities

• Worst Case Complexity for Insertion Sort is O(n²).
  The worst-case scenario occurs in insertion sort when an array is in ascending order, and you want to sort it in the opposite order, descending order. In this case, worst-case complexity occurs. In that case, each element has to be compared with the other elements, so, for every nth element, n-1 comparisons are made. Thus, the total number of comparisons = n*(n-1). This is equivalent to n².
• Best Case Complexity for Insertion Sort is O(n).
  The worst-case scenario occurs in insertion sort when the array is already sorted in the desired order, and the outer loop runs for n number of times, whereas the inner loop does not run at all because the condition will fail each time. So, there is only n number of comparisons. Thus, complexity is linear.
• Average Case Complexity for Insertion Sort is O(n²).
  It occurs when the elements of an array are in mixed order, neither ascending nor descending.
• Space Complexity

Space complexity is O(1) because an extra variable is used.

Application of Insertion Sort

The insertion sort is mostly used when the array has less number of elements and when there are only a few elements left to be sorted.