|
What is Insertion Sort in Data Structure and Algorithm?
Insertion sort is same as arranging cards one by one from right to left. First taking cards from second to last and compare the card from current place to left If it is greater than taken card move card to one step right. otherwise put the card to before of last moves.
For Example take five cards
[38, 78, 56, 2, 3]
First step...
Taking 2nd card 78. Seeing at left 36, It is not greater than 78 so putting back to same place.
[38,78,56,2,3]
Second step...
Taking 3rd card 56. Seeting at left 78, It is greater than 56. So moves 78 to right one step.
[38, ,78,2,3]
Seeting at left 38, It is not greater than 56. So putting 56 at 2nd place.
[38,56,78,2,3]
Third step...
Taking 4th card 2. Seeing at left 78. It is greater than 2. So moves 78 to right one step.
[38,56, ,78,3]
Seeing at left 56. It is greater than 2. So moves 56 to right one step.
[38, ,56,78,3]
Seeing at left 38. It is greater than 2. So moves 38 to right one step.
[ ,38,56,78,3]
At final putting 2 to 1st place
[2,38,56,78,3]
Fourth step...
Taking 5th card 3. Seeing at left 78. It is greater than 3. So moves 78 to right one step.
[2,38,56, ,78]
Seeing at left 56. It is greater than 3. So moves 56 to right one step.
[2,38, ,56,78]
Seeing at left 38. It is greater than 3. So moves 38 to right one step.
[2, ,38,56,78]
Seeting at left 2, It is not greater than 3. So putting 3 at 2nd place.
[2,3,38,56,78]
Now it is sorted..
[2,3,38,56,78]
|
Insertion sort example using JAVA import java.util.Arrays;
class Solution {
public static void main(String args[])throws Exception{
int data[] = {38,78,56,2,3};
int i,j,key;
System.out.println("Before Sorting: "+Arrays.toString(data));
for (i=1;i<data.length;i++){
key=data[i];
for (j=i-1;(j>=0 && data[j] > key);j--){
data[j+1] = data[j];
}
data[j+1] = key;
}
System.out.println("After Sorting: "+Arrays.toString(data));
}
} |
