Python program for insertion sort

In this post, you will learn about insertion sort and how to write an insertion sort program using the Python programming language.

The Insertion Sort is a very simple technique, it inserts each item in the proper place in the final list. Insertion sort is less effective as compared to the other sorting techniques. In this, the array elements are divided into two parts.

Insertion sort example

These are the insertion sorting techniques.

Search for the element that is less than the first element. A[1] < A[0], so interchange them.

Next, search for the next element that is less than the first element. A[2] < A[0], so interchange them.

Now there is no element in the right which is less than the first element. Similarly, we repeat the same process for A[1], A[2] and A[3].

While sorting of A[3], we found A[3] > A[4], so we interchange them.

Finally, we get the sorted array element.

Complexity of Insertion sort

Suppose n is the number of elements in an array.

Best Time Complexity - O(n)
Worst Time Complexity - O(n2)
Average Time Complexity - O(n2)

Insertion sort Algorithm

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for i <- lastSortedIndex down to 0
      if current element i > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

Insertion sort program in Python

In the given Python program, we create a function insertion_sort() that takes an array as an argument. Inside the function, we create a for loop with a loop variable i that counts from 1 to the length of the array. Next, we set a variable key equal to the element at index i and set j equal to i – 1. We create a while loop that runs as long as j is non-negative and key is smaller than the element at index j. Within this loop, we set the element at index j + 1 equal to the element at index j and decrement j. When the while loop finishes, we set the element at index j + 1 equal to key.

# Insertion sort in Python

def insertion_sort(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 -= 1       
         # Place key at after the element just smaller than it.
         arr[j+1] = key
       
# main
# Initializing array
arr = [42, 55, 23, 64, 12, 66, 32, 14, 16, 63]
insertion_sort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
   print (arr[i])

The sorted array is:
12
14
16
23
32
42
55
63
64
66

Related Articles