Program to use insertion sort using C/C++/Python/Java
Insertion sort- It places sorted elements at their suitable place in iteration. If we get a larger element then check with other elements whether it’s suitable at that place or not, the other unsorted one is kept on the right side. It is more simple and more adaptive in nature
In C
In this, we ask the user to input elements and check the first element with other elements and place the smallest element at the first and the unsorted ones at the end. This process takes less time and is very easy to sort the data values
#include <stdio.h>
int main()
{
int a[50], n, i, j, t;
printf("\n Enter the total Number of Elements : ");
scanf("%d", &n);
printf("\n Enter the Array Elements : "); //press enter after inserting an element
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
for(i = 1; i <= n - 1; i++)
{
for(j = i; j > 0 && a[j - 1] > a[j]; j--)
{
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
printf("\n Insertion Sort Result : ");
for(i = 0; i < n; i++)
{
printf(" %d", a[i]);
}
printf("\n");
return 0;
}
The output:
Enter the total Number of Elements : 4
Enter the Array Elements : 1
0
91
9
Insertion Sort Result : 0 1 9 91
In C++:
In this, we ask the user to input elements and check the first element with other elements and place the smallest element at the first and the unsorted ones at the end. This process takes less time and is very easy to sort the data values.
#include<iostream>
using namespace std;
int main()
{
int arr[50], n, i, j, k, e, index;
cout<<"Enter the Size for Array: ";
cin>>n;
cout<<"Enter "<<n<<" Array Elements: ";
for(i=0; i<n; i++)
cin>>arr[i];
for(i=1; i<n; i++)
{
e= arr[i];
if(e<arr[i-1])
{
for(j=0; j<=i; j++)
{
if(e<arr[j])
{
index = j;
for(k=i; k>j; k--)
arr[k] = arr[k-1];
break;
}
}
}
else
continue;
arr[index] = e;
}
cout<<"\nThe Sorted Array:\n";
for(i=0; i<n; i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
In Python:
In this, we ask the user to input elements and check the first element with other elements and place the smallest element at the first and the unsorted ones at the end. This process takes less time and is very easy to sort the data values.
def insertion_Sort(arr):
for i in range(1, len(arr)):
m = arr[i]
j = i-1
while j >=0 and m< arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = m
a = eval(input("enter a list"))
insertion_Sort(a)
print ("The sorted array is:")
print (a)
The output:
enter a list[2,7,1,4,3]
The sorted array is:
[1, 2, 3, 4, 7]
In Java:
In this, we have an array and we write a code to do the sorting. After calling the function, the array is sorted and we can change the array input for various results.
class InsertionSort {
void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int k = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > k) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = k;
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6 };
InsertionSort ob = new InsertionSort();
ob.sort(arr);
printArray(arr);
}
} The output:
5 6 11 12 13
Time and Space Complexity
Time complexity -O(N2)– for every element in an array , if it’s not arranged in proper order then it will take n2 time to sort the list.
Space Complexity- O(1) – because an extra variable is used