Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:
|
1 2 3 4 5 6 7 8 |
for i = 1 to A.length-1 key = A[i] /* insert A[i] into the sorted sequence A[0,...,j-1] */ j = i - 1 while j >= 0 and A[j] > key A[j+1] = A[j] j-- A[j+1] = key |
Note that, indices for array elements are based on 0-origin.
To illustrate the algorithms, your program should trace intermediate result for each step.
Input
The first line of the input includes an integer N, the number of elements in the sequence.
In the second line, N elements of the sequence are given separated by a single space.
Output
The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.
Constraints
1 ≤ N ≤ 100
Sample Input 1
6
5 2 4 6 1 3
Sample Output 1
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
Sample Input 2
3
1 2 3
Sample Output 2
1 2 3
1 2 3
1 2 3
Hint
Template in C
Meaning
Solution
插入排序第二层循环中是从当前处（也是未排序的这个数）向前寻找比其大的数，如果有向后移动一位。临界条件两个，1，不能再向前了（判断此刻指针下标大于0）2，有比其更小的数（判断指针是否比当前处的数小）。最后将当前数插入到指针的位置
Coding
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<iostream> using namespace std; void print(int a[], int n) { int i; for (i = 0; i < n; i++) { if (i > 0) cout<<" "; cout << a[i]; } cout << endl; } void insertionsort(int a[], int n) { int i, j, tmp; for (i = 1; i < n; i++) { tmp = a[i]; for (j = i; j > 0 && a[j - 1] > tmp; j--) a[j] = a[j - 1]; a[j] = tmp; print(a, n); } } int main() { int n; int a_list[105]; cin >> n; for (int i = 0; i < n; i++) { cin >> a_list[i]; } print(a_list, n); insertionsort(a_list, n); } |
