Please implement insertion sort algorithm to sort a sequence of number in ascending order, and show the sequence of number after each iteration.
The insertion sort algorithm is shown in following:
The array is composed of two regions, sorted region and input region. At the beginning, the first element is considered sorted.
Array: 7 5 6 8 4 3 2 1
Sorted:(7)
Input:(5, 6, 8, 4, 3, 2, 1)
At each iteration, the first element in the input region is fetched, and will be inserted into the sorted region. To find the corrected location, the fetched element is compared with each element from the end of sorted region iteratively; if the fetched element is larger than the compared one, just swap them.
For example, in the first iteration, 7 is fetched from the input region.
Array: 7 5 6 8 4 3 2 1
Sorted:(7)
Fetch: 5
Input:(6, 8, 4, 3, 2, 1)
After the first iteration, the array becomes:
Array: 5 7 6 8 4 3 2 1
Sorted:(5, 7)
Input:(6, 8, 4, 3, 2, 1)
In the second iteration, 6 is fetched:
Array: 5 7 6 8 4 3 2 1
Sorted:(5, 7)
Fetch: 6
Input:(8, 4, 3, 2, 1)
After the second iteration, the array becomes:
Array: 5 6 7 8 4 3 2 1
Sorted:(5, 6, 7)
Input:(8, 4, 3, 2, 1)
If there are N elements, N-1 iterations is needed. The Sample Output shows the full results of the example.
There are 2 lines input.
The first line contains a integer n, indicating the total number of integers would be sorted. (n <= 100000)
The second line consists of the integers being sorted.
Show the sequence of number after each iteration.
If the input has n numbers, the output would have n-1 lines.
note: print a space before each number, and print '\n' in the end of each line.