Insertion Sort

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:

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

#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);
}

​

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权

转载请注明原文链接：Insertion Sor