こんにちは！ mnbd（@mnbbbbbd）です。
AIZU ONLINE JUDGEの「ALDS1_1_A 挿入ソート」を解いてみましたので、その回答と解説をご紹介いたします。
プログラミング初心者なので、もっといい回答があるに違いありません。
あくまでも「動作はする」サンプルとしてご覧ください。
問題文
挿入ソート（Insertion Sort）は、手持ちのトランプを並び替えるときに使われる、自然で思い付きやすいアルゴリズムの１つです。片手に持ったトランプを左から小さい順に並べる場合、１枚ずつカードを取り出して、それをその時点ですでにソートされている並びの適切な位置に挿入していくことによって、カードを並べ替えることができます。
1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A2 for i が 1 から N-1 まで3 v = A[i]4 j = i - 15 while j >= 0 かつ A[j] > v6 A[j+1] = A[j]7 j--8 A[j+1] = vN 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。上の疑似コードに従いアルゴリズムを実装してください。アルゴリズムの動作を確認するため、各計算ステップでの配列（入力直後の並びと、各 i の処理が終了した直後の並び）を出力してください。
入力
入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。出力
出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。配列の要素は１つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。制約
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_A
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 1,000
解答
#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;
}感想
問題文にアルゴリズムが載っているので、文法さえ分かれば書くことはできるはず。
ただ、アルゴリズムの部分がこれまでに見たことがないような形だと感じた。
サイトにある「一般解説」で説明と図を見て理解することが必要。
単純にコードを見ただけでは何が起きているのかわからない。
まとめ
AIZU ONLINE JUDGEの「ALDS1_1_A 挿入ソート」を解いてみましたので、その回答と解説をご紹介いたします。
少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント（@mnbbbbbd）
以上です。
読んでいただきありがとうございました！