Insertion_Sort
Insertion sort is the sorting mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and then arranged simultaneously in some particular order. The analogy can be understood from the style we arrange a deck of cards. This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.
Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
##Time Complexity: O(n*2)
Pseudo Code
for(i=1;i<n;i++){ //outer loop
for(j=i; j>0 && arr[j-1]>arr[j]; j--){ //comparing adjacent numbers and if the sequential number is greater, then swap to arrange the numbers in ascending order
temp = arr[j-1];
//swapped arr[j] and arr[j-1]
arr[j-1] = arr[j];
arr[j] = temp;
}
}
Code Explaination:
User first enters the number of elements of the array.
In the first for loop we are taking input of array elements from the user.
Then in the next for loop, the first step involves the comparison of the element with its adjacent element.
And if at every comparison reveals that the element can be inserted at a particular position, then space is created for it by shifting the other elements one position to the right and inserting the element at the suitable position.
The above procedure is repeated until all the element in the array is at their apt position.
In the last loop we are printing the array which is now sorted.
Hence, you get the desired output.