In this technique, we pick an Element and then insert it at the appropriate position in ascending and descending order.
The inspiration has been taken from playing cards
Insertion sort is just like how to sort playing cards in your hands. You pick one card and try to place that card in its correct position.
The array is kind of split into a sorted part and an unsorted part. A value from the unsorted part is picked and placed into its correct position in the sorted part.
#include<stdio.h>
// Function to print array
void display(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function to run the program
int main()
{
int array[] = {8, 6, 4, 20, 24, 2, 10, 12};
int size = sizeof(array)/sizeof(array[0]);
printf("Before Insertion sort: \n");
display(array, size);
int i, key, j;
for (i = 1; i < size; i++)
{
key = array[i];
j = i - 1;
/* Here the elements in b/w arrary[0 to i-1]
which are greater than key are moved
ahead by 1 position each*/
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1;
}
// placing element at its correct position
array[j + 1] = key;
}
printf("After Insertion sort: \n");
display(array, size);
return 0;
}
// Time Complexity : O(n^2)
// Auxiliary Space : O(1)
// C++ Program for Insertion Sort
// Time Complexity : O(N^2)
// Space Compelexity : O(1)
// Best Case : When already Sorted, Worst Case : When reverse Sorted
#include<iostream>
using namespace std;
//Function to print array.
void display(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << "\t";
cout << "\n";
}
//Main function to run the program.
int main()
{
int array[] = {8, 6, 4, 20, 24, 2, 10, 12};
int size = sizeof(array)/sizeof(array[0]);
cout << "Before Insertion sort: \n";
display(array, size);
int i, key, j;
for (i = 1; i < size; i++) {
key = array[i];
j = i - 1;
/* Here the elements in b/w arrary[i-1 & 0]
which are greater than key are moved
ahead by 1 position each*/
while (j >= 0 && array[j] > key)
{
array[j + 1] = array[j];
j = j - 1; // moving backwards
}
// placing key item now
array[j + 1] = key;
}
cout << "After Insertion sort: \n";
display(array, size);
return 0;
}
// Java Program for Insertion Sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best Case : When already Sorted, Worst Case : When reverse Sorted
class Main
{
// Main method
public static void main(String args[])
{
int a[] = {8, 6, 4, 20, 24, 2, 10, 12};
System.out.println("Before Insertion Sort: ");
printArray(a);
insertionSort(a);
System.out.println("After Insertion Sort: ");
printArray(a);
}
/*Function to sort array using insertion sort*/
static void insertionSort(int arr[])
{
int len = arr.length; //calculating the length of the array
for (int i = 1; i < len; i++)
{
int key = arr[i];
int j = i - 1;
/* Shift elements of a[i-1 .... 0], that are greater
than key, to one position right of their
current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
/* A utility function to print array of size n*/
static void printArray(int a[])
{
int len = a.length;
for (int i = 0; i < len; ++i)
System.out.print(a[i] + " ");
System.out.println();
}
}
Before Insertion sort:
8 6 4 20 24 2 10 12
After Insertion sort:
2 4 6 8 10 12 20 24
| Best | Average | Worst | Space Complexity |
| O(n) | O(n2) | (n2) | O(1) |