Insertion Sort
Define(Made By my understanding not bookish 😃)
Insertion Sort is a sorting algorithm, used for sorting an array. It sort element of an array one by one by comparing it with all the previous elements as shown in the below figure :-
Explanation from the above figure.
(a) In this step the value at index 2 is less than value at index 1 the elements were swapped.
(b) In this step the value at index 3 is compared with the previous index 2 and then it is compared with the index 1 to check whether it is less than all of them.
(c) Till this step the value till index 3 are sorted now while comparing the value of index 4 with
index 3 it is greater than value at index 3 (i.e 5 < 6) so we don't have to swap the values.
(d) In this step as shown in figure (d) the value at index 5 is less than all of its previous elements so it will be swapped till index 1.
(e) In this step as shown in figure (e) the last value of the array is compared till the index where the value is greater than the number (i.e 4 > 3) then after the value at last index will come to its original position.
(f) This is the last step of Sorting Algorithm or this is in fact a sorted array.
NOTE:- As shown in the figure it is explained using index starting at 1 but in array index always start from 0. (This thing should be kept in mind).
Program Using Java
package Sorting;
// INSERTION SORT
// Note:- Index position always start with 0.
public class InsertionSort
{
public static void main(String[] args)
{
int[] arr = {50, 120, 40, 20, 10};
int j = 0;
int k = arr.length;
for(int i = 1; i < k; i++)
{
int key = arr[i];
j = i - 1;
//---------- Most Important step in entire Program "Sorting for array will start at this point---------
while(arr[j] > key)
{
arr[j+1] = arr[j];
arr[j] = key;
if(j > 0)
{
j--;
}
}
//-----------------------------------------------------------------------------------------------------------------
}
for(int i = 0; i < k; i++)
{
System.out.println(arr[i]);
}
}
}
In the above example you can take value of array of your choice you will get correct sorted array as a result.
If you want to see the program with the step by step explanation then visit to the link given below and check it.
If you have any queries regarding this algorithm then you can comment your queries I will try my best to solve them all.
Share it with your friend so that they can also understand the Insertion Sort easily.
Comments
Post a Comment