Sort given array using insertion sort.
Example 1:
Input:
N=6
arr[] = {3, 2, 9 , 1, 15, 10}
Output: {1, 2, 3, 9, 10, 15}
Example 2:
Input:
N=4
arr[] = {15. -2, 1, 18}
Output: {-2, 1, 15, 18}
1. Function insertionSort:-The insertionSort function takes an integer array arr[] and its size n as parameters.
2. Outer Loop:-
The outer loop iterates from i = 1 to i = n-1. This loop considers each element in the unsorted part of the array one by one.
3. Key Element:-For each element at index i, it is temporarily stored in the variable key.
4. Inner Loop:-
The inner loop runs from j = i - 1 to j = 0. This loop compares the element key with the elements in the sorted part of the array (elements at indices 0 to i-1).
It checks if the element at index j is greater than key. If so, it shifts the larger element to the right by one position to make room for key.
5.Placing key in Correct Position:-
Once the inner loop finishes, it means that the correct position for key has been found, and it is placed in that position (arr[j + 1] = key).
6.Main Function:-
In the main function:
The user inputs the number of elements n.
An integer array arr of size n is declared to store the input elements.
The user inputs the array elements.
The insertionSort function is called to sort the array in ascending order using the Insertion Sort algorithm.
Finally, the sorted array is printed.