問題
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_A (新しいタブで開く)
問題文
挿入ソート。
1 枚ずつカードを取り出し、それをその時点ですでにソートされている並びの適切な位置に挿入していくことで、ソートを行う。
疑似コードは以下の通り。
insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
for i が 1 から N-1 まで
v = A[i]
j = i - 1
while j >= 0 かつ A[j] > v
A[j+1] = A[j]
j--
A[j+1] = v
個の要素を含む数列 を昇順に挿入ソートしてね。
上の疑似コードにしたがってアルゴリズムを実装し、各ステップでの結果を出力してね。
制約
サンプル
I/O 1
6
5 2 4 6 1 3
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
I/O 2
3
1 2 3
1 2 3
1 2 3
1 2 3
考察
適切に C++ のコードを実装するだけ。
コード
void print(const vector<int>& a) {
rep(i, a.size()) cout << a[i] << (i == a.size() - 1 ? "\n" : " ");
}
void insertionSort(vector<int>& a, int n) {
rep(i, n - 1) {
int v = a[i + 1];
int j = i;
while (j >= 0 && a[j] > v) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = v;
print(a);
}
}
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
print(a);
insertionSort(a, n);
return 0;
}