ALDS1_1_A 挿入ソートをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ALDS1_1_A 挿入ソート」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
解答
感想
まとめ

問題文

挿入ソート（Insertion Sort）は、手持ちのトランプを並び替えるときに使われる、自然で思い付きやすいアルゴリズムの１つです。片手に持ったトランプを左から小さい順に並べる場合、１枚ずつカードを取り出して、それをその時点ですでにソートされている並びの適切な位置に挿入していくことによって、カードを並べ替えることができます。
1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
2 for i が 1 から N-1 まで
3 v = A[i]
4 j = i - 15 while j >= 0 かつ A[j] > v
6 A[j+1] = A[j]
7 j--
8 A[j+1] = v
N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。上の疑似コードに従いアルゴリズムを実装してください。アルゴリズムの動作を確認するため、各計算ステップでの配列（入力直後の並びと、各 i の処理が終了した直後の並び）を出力してください。
入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。
出力
出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。配列の要素は１つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。
制約
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 1,000
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_A

解答

#include <bits/stdc++.h>
using namespace std;

void print_array(int a[], int n) {
    for(int i = 0; i < n; i++) {
        if(i != n - 1) {
            cout << a[i] << " ";
        } else {
            cout << a[i];
        }
    }
    cout << endl;
}

int *insertion_sort(int a[], int n) {
    print_array(a, n);
    for(int i = 1; i <= n - 1; i++) {
        int v = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > v) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = v;
        print_array(a, n);
    }
    return a;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    insertion_sort(a, n);

    return 0;
}