Python Program for Insertion Sort. Writing a Python Program to implement insertion sort is a fantastic way for beginners and intermediate programmers to get hands-on experience with sorting algorithms. Insertion sort is a simple and efficient comparison-based sorting algorithm that builds the final sorted array(or list) one item at a time. Insertion sort is particularly useful for sorting a small number of elements. This tutorial will guide you through creating a Python program to perform an insertion sort.
Table of Contents
Insertion Sort
The insertion sort algorithm conceptually divides the list array into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part. This process is similar to playing cards in your hand.
Implementing Insertion Sort with Python
Defining the Insertion Sort Function
First, You need to define a function that performs the insertion sort. This function will take a list as its parameter.
def insertion_sort(arr):
# Sorting the Array/List
To sort the array/list, You will need to use two loops: An outer loop to go through each element(except the first, as it is considered sorted) and an inner loop to compare the selected element with elements in the sorted part of the array.
def insertion_sort(arr):
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 In the above code
'i'iterates through each element of the array starting from the second element.'key'is the value of the current element being sorted?'j'is used to find the correct position'key'by comparing it with each element in the sorted part of the array.- The while loop shifts elements of the sorted part that are greater than
'key'one position ahead of their current position. 'key'is placed in its correct position in the sorted part.
Complete Python Program for Insertion Sort
combining the function definition with the sorting logic, the complete Python program for selection sort looks like this-
def insertion_sort(arr):
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
list = [10,21,32,8,5,3]
insertion_sort(list)
print("Sorted array")
print(list)
Congratulations!! you have successfully written a Python program to perform insertion sort. This tutorial walked you through understanding insertion sort algorithm, Implementing it in Python, and running your program to sort an array. Insertion sort is a fundamental sorting algorithm that is efficient for small datasets and serves as a building block to understanding more complex sorting algorithms.
Happy Coding & Learning