Home
Interview Experience 
Discussion Forum
0 Notification 
Home
All Companies 
Online Classes
Paid Materials
Syllabus 
Off Campus 
Interview Exp 
CSE Insertion Sort
Insertion Sort in Java
This is an in-place comparison-based sorting algorithm, which is idle for small data-sets. Insertion sort is almost a resemblance of the way we sort playing cards in our hand. In this algorithm, we try to insert the elements of the array into an already sorted array.
- Consider that there are 5 elements in an array which are to be sorted.
- First, we consider the 0th index as sorted part and the rest is unsorted.
- Then we compare the next element of the array with the first element of the array, if the first element is smaller then the second element then we swap the elements, otherwise we place the element after the first element
- Thus each time we insert element the sorted array becomes larger and unsorted becomes smaller, and the new element is to be compare with all the previous elements of the sorted array and adjust the element just next to its smaller element.
- We repeat this process till all the elements in array become part of the sorted array
Code for Insertion Sort in Java
// Java Code for implementation of Insertion Sort
class PrepInsta
{
// Main method
public static void main(String args[])
{
int a[] = { 12,11,13,5,6 };
PrepInsta ob = new PrepInsta();
ob.sort(a);
printArray(a);
}
/*Function to sort array using insertion sort*/
void sort(int a[])
{
int len = a.length;//calculating the length of the array
for (int i = 1; i < len; i++)
{
int key = a[i];
int j = i - 1;
/* Shift elements of a[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j = j - 1;
}
a[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();
}
}
Time Complexity of Insertion Sort
Running time is an important aspect to consider when selecting a sorting algorithm since efficiency is often thought of in terms of speed. Insertion sort has an average and worst-case running time of O(n^2), so in most cases, a faster algorithm is more desirable.
Please Login/Signup to comment
comments