Sorting is a technique to arrange the data in ascending, descending order or lexicographical order. Using an efficient sorting algorithm can improve the time complexity of the code.
The insertion sort is a famous and easy problem that is asked in various product based companies and semester exams. In this article, you will learn about insertion sort with real life examples with code demonstration.
Definition of insertion sort
Insertion sort is defined as a sorting algorithm that takes the ith element and places it in the correct position in the array. The insertion sort algorithm performs the same operation on the whole array by picking the element one by one and storing it in the right place.
One real world example of insertion sort is derived from playing cards in school. When a pack of cards is taken in hand, we take one card and place it in the correct position behind the large numbers.
Another example of insertion sort algorithm is placing suits at a garment store.
Another example of insertion sort algorithm is placing suits at a garment store.
In the cupboard, the suits are placed in sorted order and the lower sized suits are placed below all the higher ones.
Advantages of insertion sort algorithm
1. Simple - The insertion sort code is easier to understand and implement.
2. Efficient for smaller data set - The algorithm sounds perfect for small sized arrays as we have not to search the exact place for the element.
3. Adaptive - The algorithm works appropriate for the sorted data sets.
Insertion sort example
Let us try to understand this algorithm working by taking the following array as an example -
Arr[] = [9, 6, 7, 3, 4]
- Operating the element arr[0]
We mark the section blue as sorted and the orange as unsorted, So we operare 9 and since this is the first element in the left array it remains sorted.
Arr[] = [9, 6, 7, 3, 4]
- Operating the element arr[1]
Now we take 6 and mark it as blue. So the left array has 2 elements 9 and 6. Since 6 is less than 9 we interchange to sort the left array.
Arr[] = [6, 9, 7, 3, 4]
- Operating the element arr[2]
Now we take 7 and mark it as blue. So the left array has 3 elements 9, 6, 7. Since 7 is less than 9 and greater than 6 we interchange to sort the left array.
Arr[] = [ 6,7, 9, 3, 4]
- Operating the element arr[3]
Now we take 3 and mark it as blue. So the left array has 4 elements 9, 6, 7, 3. Since 3 is the smallest we place it in the beginning.
Arr[] = [3, 6, 7, 9, 4]
- Operating the element arr[4]
Now we take the last element. 4 comes after 3 so we place it in second position.
Arr[] = [3, 4, 6, 7, 9]
For a better understanding in a picture mode you can visit
Pseudocode for insertion sort algorithm
insertionSortAlgorithm(array arr)
mark First element as sorted and it comes in left array
for each unsorted element A
Store the element A
for j <- lastSortedIndex down to 0
if current element j > A
move sorted element to the right by 1
break loop and insert A here
end insertionSortAlgorithm
Explanation
Line 2: The first element is single so it is already in sorted format.
Line 3: Run a loop from start to end to operate each element in the array.
Line 4: Extract the element at position i i.e. array[i]. Let it be called A.
Line 5: To compare A with its right elements by running the loop j from i-1 to 0
Line 6, 7: Compare A with the left element, if A is lesser, then move arr[j] to right by 1.
Line 8: After finding the appropriate index for A insert into that position.
C code of insertion sort algorithm
#include <stdio.h>
// Function for insertion sort
void Insertion_Sort(int array[], int size)
{
int temp, j, i;
for(i = 1; i < size; i++)
{
temp = array[i];
j = i - 1;
// Do swapping
while(j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
// Function to print elements of array
void Print_Array(int array[], int size)
{
for(int i = 0; i < size; i++)
printf("%d\t",array[i]);
printf("\n");
}
// Driver Function
int main()
{
int num;
scanf("%d", &num);
int array[num];
for (int i = 0; i < num; i++) {
scanf("%d", &array[i]);
}
Insertion_Sort(array, num);
Print_Array(array, num);
return 0;
}
Input:
num = 6
array = [1, 6, 3, 3, 5, 2]
Output:
[1, 2, 3, 3, 5, 6]
CPP Code for Insertion Sort Algorithm
#include <iostream>
using namespace std;
// Function for insertion sort
void Insertion_Sort(int array[], int size)
{
int temp, j;
for(int i = 1; i < size; i++)
{
temp = array[i];
j = i - 1;
// Do swapping
while(j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
// Function to print elements of array
void Print_Array(int array[], int size)
{
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver Function
int main()
{
int num;
cin >> num;
int array[num];
for (int i = 0; i < num; i++) {
cin >> array[i];
}
Insertion_Sort(array, num);
Print_Array(array, num);
return 0;
}
Input:
num = 6
array = [1, 6, 3, 3, 5, 2]
Output:
[1, 2, 3, 3, 5, 6]
Java Code for Insertion Sort Algorithm
import java.util.Scanner;
class Insertion_Sort_algo
{
// function for insertion sort
public static void InsertionSort(int[] array, int size)
{
int temp, j;
for(int i = 1; i < size; i++)
{
temp = array[i];
j = i - 1;
// Do swapping
while(j >= 0 && array[j] > temp)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
// function to print array
public static void Print_Array(int[] array, int size)
{
for(int i = 0; i < size; i++)
System.out.print(array[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int num;
Scanner s = new Scanner(System.in);
num = s.nextInt();
int array[] = new int[num];
for (int i = 0; i < num; i++) {
array[i] = s.nextInt();
}
InsertionSort(array, num);
Print_Array(array, num);
}
}
Input:
num = 6
array = [1, 6, 3, 3, 5, 2]
Output:
[1, 2, 3, 3, 5, 6]
Time Complexity of Insertion Sort Algorithm
From the code we have seen that insertion sort performs two operations - iterating in the right array and interchanging with the left one. This combined operation contributes to the time complexity of the algorithm.
- Best case
In best case the time complexity of insertion sort algorithm is O(N). This is the case when the whole array is already sorted. It becomes N case time complexity as the inner loop never gets executed. The outer loop will check and scan for each element which makes the time complexity to O(N).
- Worst case
The worst case time complexity is O(N*N). This is the case when the whole array is unsorted. In this case the inner loop will be executed till the end of the right array in order to place the arr[i] in the correct position.
- Average case
The average case time complexity is O(N*N). In this case, elements are mixed up neither fully sorted nor fully unsorted.
Space Complexity of Insertion Sort Algorithm
The space complexity of insertion sort algorithm is constant as it takes only one or two variables in the entire array. So, the space complexity of insertion sort algorithm is O(1).
Read more about Insertion Sort on Scaler Topics.
Happy Learning!
Top comments (0)