INSERTION SORT
Hey guys we are back with
another blog! And today we are talking about insertion sorting in java, so have
a read through and do let us know your
views in the comment section below.
So insertion sorting in one of
the three basic sorting in java (i.e., bubble sort, selection sort and
insertion sort). In insertion sort we sort an array by comparing an element
with the previous index elements in that array. So let’s understand this
sorting algorithm more closely.
Suppose we have an array {7,3,5,2} and we intend to sort it , so
the insertion sort will take place as follows
We will start by comparing the
index 1 (i=1) with the previous index element i.e., 0 (j=i-1)
and then we will progress by incrementing the value of i and then
compare the element present at ith index with the previous
index values.
So for the given array we will
first compare ar[i]=3 (here i=1) with ar[j]=7 (here j=i-1, so j=0)
1st iteration : initially
ar[0]>ar[1] , we will swap the two values so the resulting array will be :
{3,7,5,2}
2nd iteration:
ar[2]<ar[1] , we will also check that is ar[2]<ar[0]?, in this case it’s
not so we will swap 7 and 5 for now:
{3,5,7,2}
3rd iteration: ar[3]<ar[2], ar[3]<r[1],
ar[3]<ar[0], so we put 2 in the beginning and the shift all the elements to
+1 of their current index :
{2,3,5,7}
So that was basically how
insertion sorting takes place, now let’s see a code that implements out
insertion sorting with a bit larger array.
public class InsertionSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int ar[] =
{7,3,5,2,4,1,6};
int n = ar.length;
int temp,j;
for(int i=1; i<n; i++)
{
//storing
the elements at index 1 in a temp variable
temp= ar[i];
j=i-1;
while(j>=0
&& ar[j]>temp)
{
//we
will shift the elements to right if temp value is smaller tham
a[j]
ar[j+1]=ar[j];
j--;
}
ar[j+1]=temp;
}
//printing
the sorted array
System.out.println("Sorted array:");
for(int i=0; i<n; i++)
System.out.print(ar[i]+" ");
/* Sorted
array:
1 2 3 4 5 6 7
*/
}
}
