寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C #ALDS1_1_A Insertion Sort

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムです。

・問題
 挿入ソート(Insertion Sort)は、手持ちのトランプを並び替えるときに使われる、自然で思い付きやすいアルゴリズムの1つです。
 片手に持ったトランプを左から小さい順に並べる場合、1枚ずつカードを取り出して、それをその時点ですでにソートされている並びの適切な位置に挿入していくことによって、カードを並べ替えることができます。
 挿入ソートは次のようなアルゴリズムになります。
f:id:neguse_atama:20200422195225p:plain
 N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。
 上の疑似コードに従いアルゴリズムを実装してください。
 アルゴリズムの動作を確認するため、各計算ステップでの配列(入力直後の並びと、各 i の処理が終了した直後の並び)を出力してください。

・入力される値
 入力の最初の行に、数列の長さを表す整数 N が与えられます。
 2 行目に、N 個の整数が空白区切りで与えられます。

・期待する出力
 出力は N 行からなります。
 挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。
 配列の要素は1つの空白で区切って出力してください。
 最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。

・条件
   1 ≤ N ≤ 100
   0 ≤ A の要素 ≤ 1,000

僕が作成、提出したコードは、以下のとおりです。

/*
 ALDS1_1_A Insertion Sort
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<stdio.h>
void InsertionSort(int a[],int n){
    int loop,loop2,swap;
    for(loop=1;loop<n;loop++){
        for(loop2=0;loop2<n;loop2++){
            printf("%d",a[loop2]);
            if(loop2!=n-1){
                putchar(' ');
            }else{
                putchar('\n');
            }
        }
        swap=a[loop];
        loop2=loop-1;
        while(loop2>=0 && a[loop2]>swap){
            a[loop2+1]=a[loop2];
            loop2--;
        }
        a[loop2+1]=swap;
    }
}
int main(void){
    int n,a[101],loop;
    scanf("%d",&n);
    for(loop=0;loop<n;loop++){
        scanf("%d",&a[loop]);
    }
    InsertionSort(a,n);
    for(loop=0;loop<n;loop++){
        printf("%d",a[loop]);
        if(loop!=n-1){
            putchar(' ');
        }else{
            putchar('\n');
        }
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_1_A Insertion Sort