A - Insertion Sort

問題

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

$N$ 個の要素を含む数列 $A$ を昇順に挿入ソートしてね。
上の疑似コードにしたがってアルゴリズムを実装し、各ステップでの結果を出力してね。

制約

• $1 \le N \le 100$
• $0 \le A_i \le 1000$

サンプル

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++ のコードを実装するだけ。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_1_A/judge/6379607/C++17

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