As we know, sorting is the process of arranging a collection of items or data elements in a particular order, such as increasing or decreasing values. The goal is to make it easier to find, access, or analyze the data. Sorting helps bring order to unorganized information, allowing for efficient searching, comparison, and retrieval of specific items within the data set. There are various types of algorithms, but in this article we are going to discuss the Insertion Sort Algorithm. And the working process of Insertion Sort Algorithm.

Insertion Sort Algorithm

Insertion Sort is a simple and efficient sorting algorithm that works by building a sorted list one element at a time. It’s particularly useful for small lists or partially sorted lists. It like arranging cards in your hand. You start with one card, and then you pick the next card and insert it into the right place among the cards you already have. You keep doing this until all cards are in order. It’s good for small or nearly sorted sets because you don’t need to move lots of cards around like in other games. This way, you gradually build a sorted arrangement from the start to the end.

Here are some common steps to how the Insertion Sort algorithm works:

1. Start with the second element (index 1) and consider it as the “current” element.
2. Compare the “current” element with the elements in the sorted subarray to its left.
3. If the “current” element is smaller (or larger, depending on the sorting order) than an element in the sorted subarray, shift that element to the right.
4. Repeat step 3 until you find the correct position for the “current” element in the sorted subarray.
5. Insert the “current” element into its correct position in the sorted subarray.
6. Move to the next unsorted element and repeat steps 2-5 until all elements are sorted.

Working of Insertion Sort Algorithm

To understand the working procedure of Insertion Sort Algorithm, we take an example of an array [15, 13, 16 , 5, 6]. As you can see in this image below, then we provide step by step solutions. So, let’s get ready to sort this array.

Here’s the step-by-step process to sort the given array [15, 13, 16, 5, 6] using the Insertion Sort algorithm:

Pass – 1

• The Key element is 13
• Compare with elements before the key element: 15
• Swap 15 and 13
• Now, the array after Pass 1: [13, 15, 16, 5, 6]

Pass – 2

• Key element: 16
• Compare with elements before the key element: 15
• No swap needed, as 16 is already greater than 15 Array after Pass 2: [13, 15, 16, 5, 6]

Pass – 3

• Key element: 5
• Compare with elements before the key element: 16, 15, 13
• Swap 16, 15, and 13 to make space for 5
• Place 5 in its correct position Array after Pass 3: [5, 13, 15, 16, 6]

Pass – 4

• Key element: 6
• Compare with elements before the key element: 16, 15
• Swap 16 and 6
• Compare with elements before the key element: 15, 13
• Swap 15 and 6
• Compare with elements before the key element: 13, 5
• Swap 13 and 6
• Place 6 in its correct position Array after Pass 4: [5, 6, 13, 15, 16]

The array is now sorted using the Insertion Sort algorithm. Each pass involves comparing the key element with elements before it and shifting them to the right until the correct position for the key element is found.

Python Program to Sort an Array Using Insertion Sort Algorithm

Here we have a Python program which implements the Insertion Sort algorithm to sort an 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

# Example usage
arr = [15, 13, 16, 5, 6]
print("Original array:", arr)
insertion_sort(arr)
print("Sorted array:", arr)

Output

Original array: [15, 13, 16, 5, 6]
Sorted array: [5, 6, 13, 15, 16]

Java Program to Sort an Array Using Insertion Sort Algorithm

public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

public static void main(String[] args) {
int[] arr = {15, 13, 16, 5, 6};
System.out.print("Original array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();

insertionSort(arr);

System.out.print("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}

Output

Original array: 15 13 16 5 6 
Sorted array: 5 6 13 15 16

We hope that you like this tutorial. If you like this, you will probably like the next ones. So bookmark our blog APalgorithm. Here you find a lot of algorithms and programming concepts like that. Thanks for reading!

Suggested Readings

• APalgorithm Basics
• DFS Algorithm Explained
• Sorting Techniques Tutorials Point

Anshul Pal

Hey there, I’m Anshul Pal, a tech blogger and Computer Science graduate. I’m passionate about exploring tech-related topics and sharing the knowledge I’ve acquired. With two years of industry expertise in blogging and content writing, I’m also the co-founder of HVM Smart Solution. Thanks for reading my blog – Happy Learning!